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 <= 58The 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) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
There is a simple O(n) solution to this problem.
You may check the breaking results of <i>n</i> ranging from 7 to 10 to discover the regularities.
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.
1def integerBreak(n):
2 if n <= 3:
3 return n - 1
4 dp = [0] * (n + 1
This Python solution applies a bottom-up DP approach where dp[i] stores the maximum product obtainable for integer i. The outer loop iterates through numbers from 4 to n, while an inner loop splits i into two parts to find the optimal product.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Integer Break is a common interview-style problem because it tests dynamic programming intuition and mathematical reasoning. Variations of this problem or similar integer partition questions frequently appear in technical interviews.
The optimal approach often uses a mathematical observation that splitting the number into as many 3s as possible maximizes the product. This greedy insight leads to a constant-time solution. Dynamic programming is another common approach used to understand the pattern and compute results for all smaller integers.
Mathematically, splitting numbers into 3s yields a higher product compared to using larger chunks. For example, 3 × 3 is greater than 2 × 4 for the same total. This property leads to the greedy strategy used in the optimized solution.
The dynamic programming solution typically uses a one-dimensional array where each index stores the maximum product achievable for that integer. This array allows previously computed results to be reused when evaluating larger numbers.
This C code snippet uses a mathematical approach to solve the integer break problem. Instead of solving it iteratively, we repeatedly factor out 3 from the integer until the remaining integer is less or equal to 4, at which point the product is simply multiplied by the final remainder.