Integer Break

Description

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.

Solutions

My solution

$dp[i]$ : maximum product by splitting $i$ into at least 2 integers.

There are $i - 2$ ways (exclusive) to split $i$ : split $i$ such that the numbers contain $j$, $0 < j < i$.

Therefore, $dp[i] = \max_{0 < j < i}(\max(j, dp[j]), i - j)$

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            for(int j = 1; j < i; ++j){
                dp[i] = max(dp[i], max(j, dp[j]) * (i - j));
            }
        }
        return dp[n];
    }
};

Optimal solution

Claims:

1. The factors (integers) must be either 2 or 3.

2. There are at most two 2s.

Proof:

1. For any factor f larger than 3, we can further split the factor f to produce a new product that is at least as good as the old product.

   1. If f is even, split f to two f/2 s. $\frac{f}{2} \cdot \frac{f}{2} \ge f$, for $f \ge 4$.
   2. If f is odd, split f into (f-1)/2 and (f+1)/2. $\frac{f-1}{2} \cdot \frac{f+1}{2} \ge f$, for $f \ge 5$.
2. If there are more than two 2s, then we can replace three 2s to two 3s to increase the product. That is because $2^3 < 3^2$.
3. How to come up with claim 1?

   1. Suppose we are allowed to split n into any rational numbers.

   2. By the Inequality of Square-Arithmetic and Geometric Means, if we split n to k numbers, the product is maximized when the k numbers are equal.

   3. So we want to find $\max_{k} (\frac{n}{k})^k$. Let $y =(\frac{n}{k})^k$. It is easy to show that $y$ is maximized when $k = \frac{n}{e}$. Therefore, the numbers are $e$.
   4. But we are only allowed to split n to integers. So we use the integers close to $e$, i.e., 2 and 3.

class Solution {
public:
    int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n % 3 == 0) return pow(3, n / 3);
        if(n % 3 == 1) return 4 * pow(3, (n - 4) / 3); // two 2s
        return 2 * pow(3, (n - 2) / 3); // one 2
    }
};

References:

1. A simple explanation of the math part and a O(n) solution

2. Why factor 2 or 3? The math behind this problem.

3. O(log(n)) Time solution with explanation