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
: maximum product by splitting into at least 2 integers.
There are ways (exclusive) to split : split such that the numbers contain , .
Therefore,
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:
The factors (integers) must be either 2 or 3.
There are at most two 2s.
Proof:
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.
If f is even, split f to two f/2 s. , for .
If f is odd, split f into (f-1)/2 and (f+1)/2. , for .
If there are more than two 2s, then we can replace three 2s to two 3s to increase the product. That is because .
How to come up with claim 1?
Suppose we are allowed to split n into any rational numbers.
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.
So we want to find . Let . It is easy to show that is maximized when . Therefore, the numbers are .
But we are only allowed to split n to integers. So we use the integers close to , 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