Leetcode 343: Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

Problem Analysis:

Suppose we break n into k numbers, a1, …, ak, according to AM-GM inequality, (a1 + a2 + … + ak) / k ≥ exp(a1 a2 … ak, 1/k), and when a1 = a2 = … = ak, product of a1 a2 … ak is the maximum value.

So we let f(x) = x^(n/x), the problem is equivalent to find maximum value of f(x). The derivative function f’(x) = n(1-lnx)x^(n/x-2). When f(x) close to maximum value, the derivative function f’(x) must close to 0. Because x must be an integer, so x is 2 or 3.

Solution:

class Solution {
public:
    int integerBreak(int n) {
        if (n < 4) return n - 1;
        
        int k = n / 2;
        if (n % 2 == 1) --k;
        long long result = pow(2, k);
        if (n % 2 == 1) result *= 3;
        
        k = n / 3;
        if (n % 3 == 1) --k;
        long long result2 = pow(3, k);
        if (n % 3 == 1) result2 *= 4;
        else if (n % 3 != 0) result2 *= 2;
        
        return max(result, result2);
    }
};

Time Complexity: O(1)

Space Complexity: O(1)