Simple Solution With Detailed Explanation, No DP Needed.


  • 1
    W

    If my calculations are right, the perfect number should be e (2.718).

    However we cannot use this number.

    This condition actually is much easier because all the integers larger than 3 can be broken into only 3s and 2s without 1s.
    For example

    4 = 2 + 2
    5 = 3 + 2
    6 = 3 + 3
    ...
    13 = 3 + 3 + 3 + 2 + 2
    

    Whenever you combine two 3s or a 3 and a 2, the product becomes smaller. So you don't combine them.

    For example:

    16 = 3 + 3 + 3 + 3 + 2 + 2
    or 
    16 = 6 + 6 + 2 + 2
    or 
    16 = 6 + 5 + 5
    because 6 < 3 * 3,  6 * 6 < 3 * 3 * 3 *3.
    because 5 < 2 * 3,  5 * 6 < 2 * 3 * 3 *3.
    

    It is obvious you don't want a combination.

    Then how many 3s you want to have?
    As many as possible unless you produce a 1. If you have a 1, then substitute one 3-and-1 pair with a 2-and-2 pair.
    For example:

    7 = 3 + 3 + 1 = 3 + 2 + 2
    

    if you spare some room for 2s, the product becomes smaller again.

    For example:

    2 * 2 * 2 < 3 * 3
    

    Then the solution is simple:

    1. Use as many 3 as possible
    2. Avoid 1
    class Solution(object):
        def integerBreak(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 2:
                return 1
            elif n == 3:
                return 2
            k = n / 3
            m = n % 3
            if m == 1:
                return 4 * (3 ** (k-1))
            elif m == 2:
                return 2 * (3 ** k)
            else:
                return 3 ** k
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.