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]dp[i] : maximum product by splitting ii into at least 2 integers.

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

Therefore, dp[i]=max0<j<i(max(j,dp[j]),ij)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. f2f2f\frac{f}{2} \cdot \frac{f}{2} \ge f, for f4f \ge 4.

    2. If f is odd, split f into (f-1)/2 and (f+1)/2. f12f+12f\frac{f-1}{2} \cdot \frac{f+1}{2} \ge f, for f5f \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 23<322^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 maxk(nk)k\max_{k} (\frac{n}{k})^k. Let y=(nk)ky =(\frac{n}{k})^k. It is easy to show that yy is maximized when k=nek = \frac{n}{e}. Therefore, the numbers are ee.

    4. But we are only allowed to split n to integers. So we use the integers close to ee, 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:

Last updated