# Integer Break
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/integer-break)
Canonical: https://scaleengineer.com/dsa/problems/integer-break
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
Given an integer `n`, break it into the sum of `k` **positive integers**, where `k >= 2`, and maximize the product of those integers.

Return _the maximum product you can get_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `2 <= n <= 58`

# Approaches
## Brute-Force Recursion
This is a direct recursive solution that explores all possible ways to partition the integer `n`. For any number `k`, it tries every possible first part `j` and recursively solves for the remaining part `k-j`. This leads to an exponential number of computations as subproblems are solved repeatedly without any caching.
**Time:** O(2^n) - The time complexity is exponential because each call can result in multiple recursive calls, leading to a tree of computations where subproblems are repeatedly solved. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n`.
**Pros:** Simple to understand as it directly translates the problem's recursive structure.
**Cons:** Extremely inefficient due to a large number of redundant computations.; Will result in a 'Time Limit Exceeded' error on most platforms for moderately large `n` (e.g., n > 20).
### Explanation
The core idea is to define a function `solve(k)` that returns the maximum product for breaking integer `k`. To compute `solve(k)`, we iterate through all possible first numbers `j` from `1` to `k-1`. For each `j`, the remaining part is `k-j`. We have two choices for this remaining part:
1. Use `k-j` as a factor directly. The product is `j * (k-j)`.
2. Break `k-j` further by calling `solve(k-j)`. The product is `j * solve(k-j)`.
We take the maximum of these two choices for each `j` and then the maximum over all possible `j`. The recurrence relation is `solve(k) = max_{1 <= j < k} (j * max(k-j, solve(k-j)))`. This approach is very slow because it re-calculates the solution for the same subproblems multiple times, leading to an exponential time complexity.

```java
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        return solve(n);
    }
    
    private int solve(int num) {
        if (num <= 3) {
            return num;
        }
        int maxProd = 0;
        for (int i = 1; i < num; i++) {
            // For the number `num`, we can break it into `i` and `num-i`.
            // We can either use `num-i` as is, or break it further.
            // The max product for breaking `num-i` is `solve(num-i)`.
            // So we take the max of `num-i` and `solve(num-i)`.
            int currentProd = i * Math.max(num - i, solve(num - i));
            if (currentProd > maxProd) {
                maxProd = currentProd;
            }
        }
        return maxProd;
    }
}
```
### Algorithm
- Create a recursive function `solve(k)` that computes the maximum product for integer `k`.
- The base case for the recursion is that for any subproblem `num <= 3`, it's optimal to not break it further, so we return `num` itself.
- For a given `num`, iterate through all possible first parts `i` from `1` to `num-1`.
- For each `i`, the remaining part is `num-i`. The product can be either `i * (num-i)` or `i * solve(num-i)` if we break `num-i` further. We take the maximum of these two possibilities.
- The function returns the maximum product found across all choices of `i`.
- The main function handles the edge cases `n=2` and `n=3` separately, as `n` must be broken into at least two parts, and then calls the recursive function for `n`.

## Bottom-Up Dynamic Programming
The brute-force recursive approach suffers from re-computing solutions to the same subproblems. We can optimize this using dynamic programming. Instead of a top-down recursive approach, we can use a bottom-up iterative approach. We build up the solution for larger integers using the already computed solutions for smaller integers, storing them in a DP table.
**Time:** O(n^2) - We have two nested loops. The outer loop runs from `2` to `n`, and the inner loop runs up to `n-1` times. · **Space:** O(n) - We use an array of size `n+1` to store the results of subproblems.
**Pros:** Guarantees finding the optimal solution by exploring all possibilities systematically.; Much more efficient than the brute-force approach, with a polynomial time complexity.
**Cons:** While much better than brute force, it is not the most optimal solution.; It requires O(n) extra space for the DP table.
### Explanation
We use an array, `dp`, where `dp[i]` stores the maximum product for breaking the integer `i`. We iterate from `i = 2` up to `n`, calculating `dp[i]` at each step. To calculate `dp[i]`, we consider all possible ways to make the first break: `i = j + (i-j)`, where `j` ranges from `1` to `i-1`. For each `j`, the product is `j` times the best we can do with the remaining `i-j`. The best we can do with `i-j` is either not breaking it further (using `i-j` itself) or breaking it further (which yields a product of `dp[i-j]`). So, for each `j`, the candidate product is `j * max(i-j, dp[i-j])`. `dp[i]` will be the maximum of these candidate products over all possible `j`. The final answer is `dp[n]`.

```java
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        // dp[i] will store the maximum product for breaking integer i.
        dp[1] = 1; // Base case for the recurrence.
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // Candidate product is j * (best result for i-j).
                // Best for i-j is either i-j itself or its broken-down product dp[i-j].
                int currentProduct = j * Math.max(i - j, dp[i - j]);
                dp[i] = Math.max(dp[i], currentProduct);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`, where `dp[i]` will store the maximum product for integer `i`.
- Initialize `dp[1] = 1` as a base for the recurrence.
- Iterate with a loop for `i` from `2` to `n` to compute `dp[i]` for each integer.
- Inside this loop, use another loop for `j` from `1` to `i-1` to represent the first part of the break.
- For each break `i = j + (i-j)`, the candidate product is `j * max(i-j, dp[i-j])`. The `max` here considers both not breaking `i-j` and breaking it optimally.
- Update `dp[i]` with the maximum product found among all possible values of `j`.
- After the loops, `dp[n]` contains the final answer.

## Mathematical Greedy Approach
This approach is based on a mathematical observation about which numbers are optimal factors. By analyzing the problem, we can deduce that the optimal factors should only be 2s and 3s. Any factor `f >= 4` can be replaced by smaller factors to get a larger or equal product. Furthermore, using 3s is generally better than using 2s. This leads to a greedy strategy of breaking `n` into as many 3s as possible.
**Time:** O(log n) - The time complexity is dominated by the `Math.pow` function, which is typically implemented using exponentiation by squaring. · **Space:** O(1) - This approach uses a constant amount of extra space, regardless of the input `n`.
**Pros:** Extremely efficient with constant space and logarithmic time complexity.; Provides a direct formula for the solution for `n > 3`.
**Cons:** The logic is not immediately obvious and requires mathematical insight to prove its correctness.
### Explanation
The core insight is that we should decompose `n` into a product of as many 3s as possible. Any integer factor `f >= 4` is suboptimal because it can be replaced by `2` and `f-2`, and `2*(f-2) >= f`. This means we only need to consider factors of 2 and 3. Comparing 2s and 3s, `3+3=6` gives a product of `9`, while `2+2+2=6` gives a product of `8`. Thus, using 3s is preferable. Based on this, the strategy is to use as many 3s as we can and use 2s to handle the remainder.

We analyze the remainder of `n` when divided by 3:
- If `n % 3 == 0`: `n` can be broken into `n/3` threes. Product: `3^(n/3)`.
- If `n % 3 == 1`: `n = 3k + 1`. A factor of 1 is bad. We regroup as `3(k-1) + 4`. Product: `3^(k-1) * 4`.
- If `n % 3 == 2`: `n = 3k + 2`. We break it into `k` threes and one 2. Product: `3^k * 2`.

Small values of `n` (`n=2, n=3`) are special cases because `n` must be broken into at least two parts.

```java
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        if (n % 3 == 0) {
            return (int) Math.pow(3, n / 3);
        }
        if (n % 3 == 1) {
            // n = 3k + 1 = 3(k-1) + 4
            return (int) Math.pow(3, (n / 3) - 1) * 4;
        }
        // n % 3 == 2
        // n = 3k + 2
        return (int) Math.pow(3, n / 3) * 2;
    }
}
```
### Algorithm
- First, handle the small base cases: if `n <= 3`, the answer is `n-1`.
- For `n > 3`, analyze the remainder of `n` when divided by 3.
- If `n % 3 == 0`, the optimal break is into `n/3` parts of `3`. The product is `3^(n/3)`.
- If `n % 3 == 1`, breaking into `3k+1` is suboptimal. It's better to form `3(k-1) + 4`. The product is `3^((n/3)-1) * 4`.
- If `n % 3 == 2`, the optimal break is `n/3` parts of `3` and one part of `2`. The product is `3^(n/3) * 2`.
- Use `Math.pow()` to calculate the powers of 3.

# Solutions
### CSharp

```csharp
public class Solution {
    public int IntegerBreak(int n) {
        int[] f = new int[n + 1];
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = Math.Max(Math.Max(f[i], f[i - j] * j), (i - j) * j);
            }
        }
        return f[n];
    }
}
```

### Java

```java
class Solution { public int integerBreak ( int n ) { if ( n < 4 ) { return n - 1 ; } if ( n % 3 == 0 ) { return ( int ) Math . pow ( 3 , n / 3 ); } if ( n % 3 == 1 ) { return ( int ) Math . pow ( 3 , n / 3 - 1 ) * 4 ; } return ( int ) Math . pow ( 3 , n / 3 ) * 2 ; } }
```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var integerBreak = function (n) {
  const f = Array(n + 1).fill(1);
  for (let i = 2; i <= n; ++i) {
    for (let j = 1; j < i; ++j) {
      f[i] = Math.max(f[i], f[i - j] * j, (i - j) * j);
    }
  }
  return f[n];
};

```

### CPP

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

### Python

```python
class Solution : def integerBreak ( self , n : int ) -> int : if n < 4 : return n - 1 if n % 3 == 0 : return pow ( 3 , n // 3 ) if n % 3 == 1 : return pow ( 3 , n // 3 - 1 ) * 4 return pow ( 3 , n // 3 ) * 2
```