9 line elegant Python solution with explanation from engineer perspective


  • 0
    R

    Let's start with simple cases, "->" means decompose:
    2 -> 1 1 = 1
    3 -> 1 2 = 2
    4 -> 2 2 = 4
    5 -> 2 3 = 6
    6 -> 3 3 = 9
    7 -> 3 2 2 = 12
    8 -> 3 3 2 = 18
    9 -> 3 3 3 = 27
    10 -> 3 3 2 2 = 36
    It's easy to know that 2 and 3 are greater than their decompositions. Every number except 2 and 3 should be decompose since this action will maximize result.
    So the code is pretty simple. We maintain a list named "factor" to store factors in every steps, and then update the min item by one if it wouldn't exceed 4 (only 2 and 3 are allowed). For example, when we update 9 (factors: 3 3 3), the min item is 3, if I update it to 4, it would exceed our role. So we delete 3 and add two 2 to the list. So the result after update is (factors: 3 3 2 2)
    '''
    def integerBreak(self, n):
    factor = [1,1]
    for i in range(3,n+1):
    # find the min item to update
    update = factor.index(min(factor))
    if factor[update]==3:
    # cannot add anymore, replace it with [2,2]
    del factor[update]
    factor+=[2,2]
    else:
    factor[update]+=1
    return reduce(lambda x,y:x*y,factor)
    '''


Log in to reply
 

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