#343 Integer Break - Solution

The goal of Integer Break is to split a given integer n into at least two positive integers such that their product is maximized. Two common strategies help solve this problem efficiently: Dynamic Programming and a mathematical greedy insight.

With Dynamic Programming, you build a table where each index represents the maximum product obtainable for that number. For each i, try splitting it into j and i - j, and compare the direct product with previously computed optimal values. This approach helps explore all valid partitions while reusing earlier results.

A mathematical observation further simplifies the problem: breaking numbers into smaller parts—especially 3s—tends to produce the largest product. This insight leads to a greedy strategy that significantly reduces computation.

The DP method runs in O(n²) time with O(n) space, while the math-based greedy solution can achieve O(1) time and space.

Approach	Time Complexity	Space Complexity
Dynamic Programming	O(n^2)	O(n)
Mathematical / Greedy Insight	O(1)	O(1)

Solutions (12)

Dynamic Programming Approach

The dynamic programming approach involves creating an array dp where dp[i] represents the maximum product obtainable for the integer i. The idea is to iterate through numbers from 2 to n and for each number, explore all possible ways to split it into two positive integers j and i-j. The solution for each i is derived by taking the maximum of j * (i-j) or j * dp[i-j] for all j from 1 to i-1.

Time Complexity: O(n^2) because of the nested loop iterating through i and j.
Space Complexity: O(n) for the dp array.

C C++Java Python C#JavaScript

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int integerBreak(int n) {
6    if (n <= 3) return n - 1;
7    vector<int> dp(n + 1, 0);
8    dp[2] = 1;
9    dp[3] = 2;
10    for (int i = 4; i <= n; ++i) {
11        for (int j = 1; j < i; ++j) {
12            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
13        }
14    }
    return dp[n];
}

int main() {
    int n = 10;
    cout << "Maximum product for " << n << " is " << integerBreak(n) << endl;
    return 0;
}

Explanation

In this C++ solution, we use a vector dp to store the maximum products, similar to the C example. For each integer i, we determine the optimal split by iterating through possible splits and updating the value at dp[i].

Mathematical Approach

The mathematical approach relies on the observation that numbers are best broken down into 2s and 3s to maximize their product. In particular, the number 3 plays a critical role. For any number greater than 4, it is beneficial to use as many 3s as possible, because any larger piece can be expressed as 3k + r, where adding more 3s generally yields a larger product (e.g., breaking 4 into 2 + 2 is optimal, compared to using one 3 and a 1). The approach is to keep factoring out 3 from n as long as the remaining part is not less than 4, then multiply the results together to get the maximum product.

Time Complexity: O(log n), as we repeatedly subtract 3.
Space Complexity: O(1) since no extra space is used besides variables.

C C++Java Python C#JavaScript


public class Solution {
    public int IntegerBreak(int n) {
        if (n <= 3) return n - 1;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        return product * n;
    }

    public static void Main(string[] args) {
        int n = 10;
        Console.WriteLine("Maximum product for " + n + " is " + new Solution().IntegerBreak(n));
    }
}