Math Python O(1) solution


  • 0

    Solve d(n/x)^x/dx = 0 we get ln(n/x) = 1, i.e. when x = e we get max product.
    And we want it in integer, so the partition will be either 2 or 3 (e ~= 2.718).

    def integerBreak(self, n):
        ret = max((2 + n & 1) * 2 ** (n//2 - 1),
    	      (3 + n % 3) * 3 ** (n//3 - 1),
                  (    n % 3) * 3 ** (n//3    ))
        return 1 if n == 2 else 2 if n == 3 else ret
    

  • 0
    D

    A perfect answer


Log in to reply
 

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