Integer Break LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Citadel Facebook Google TCSViews 3532

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)

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »