# 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)$$&#x20;

```cpp
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](https://artofproblemsolving.com/wiki/index.php?title=Root-Mean_Square-Arithmetic_Mean-Geometric_Mean-Harmonic_mean_Inequality), 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.

```cpp
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](https://leetcode.com/problems/integer-break/discuss/80689/A-simple-explanation-of-the-math-part-and-a-O\(n\)-solution)
2. [Why factor 2 or 3? The math behind this problem.](https://leetcode.com/problems/integer-break/discuss/80721/Why-factor-2-or-3-The-math-behind-this-problem.)
3. [O(log(n)) Time solution with explanation](https://leetcode.com/problems/integer-break/discuss/80785/O\(log\(n\)\)-Time-solution-with-explanation)