# Integer Break LeetCode Solution

Difficulty Level Medium

## Problem Statement

Integer Break LeetCode Solution – Given an integer `n`, break it into the sum of `k` positive integers, where `k >= 2`, and maximize the product of those integers.

We need to Return the maximum product we can get.

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

## Explanation

To find the max product of 8, break up 8 into the sum of two terms (keep the first term less than or equal to the second to prevent redundancy):

```1 + 7 --> 1 * 7 = 7 2 + 6 --> 2 * 6 = 12 3 + 5 --> 3 * 5 = 15 4 + 4 --> 4 * 4 = 16```

From this, it seems that the max product is 16, however, we neglected to also break up each of the two terms into more terms, and check all those. Let’s break the 6 into 3 + 3:

`2 + 6 = 2 + 3 + 3 --> 2 * 3 * 3 = 18`

which ends up being the correct answer. But another way to get this is to reuse the previously computed max product of 6, which we know to be 9:

```2 * (3 * 3) = 2 * max_product_of_6 = 2 * 9 = 18 ```

So for each choice of i and j with i <= j and i + j = n, check i * j but ALSO check if the previously computed max products for i and j are larger than i and j. Start with n = 1 and build-up to the final n. Store the previously computed values in a dp array.

## Code

### Java Code for Integer Break LeetCode Solution

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

### C++ Code for Integer Break LeetCode Solution

```class Solution {
public:
int integerBreak(int n) {

if (n <= 2)
return 1;

vector<int> maxArr(n+1, 0);
maxArr[1] = 0;
maxArr[2] = 1; // 2=1+1 so maxArr[2] = 1*1

for (int i=3; i<=n; i++) {
for (int j=1; j<i; j++) {
maxArr[i] = max(maxArr[i], max(j*(i-j), j*maxArr[i-j]));
}
}
return maxArr[n];
}
};```

### Python Code for Integer Break LeetCode Solution

```class Solution(object):
def integerBreak(self, n):
dp = [None, 1]
for m in range (2, n + 1):
j = m - 1
i = 1
max_product = 0
while i <= j:
max_product = max(max_product, max(i, dp[i]) * max(j, dp[j]))
j -= 1
i += 1
dp.append(max_product)
return dp[n]```

## Complexity Analysis

### Time Complexity

Since for each “i” we calculate from 1 to “i” so the time complexity comes out to be O(n^2)

### Space Complexity

We use a dp array of size n so the space complexity will be O(n)

Translate »