Integer Break - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given an integer n, break it into the sum of at least two positive integers such that the product of those integers is maximized. The task is to return the maximum possible product you can obtain from any valid split.
Approach 1: Dynamic Programming (O(n2) time, O(n) space)
This approach builds the solution bottom-up using dynamic programming. Define dp[i] as the maximum product obtainable by breaking integer i. For every number from 2 to n, iterate through all possible first splits j where 1 ≤ j < i. For each split, compute the best product using either the raw value (i - j) or the previously computed value dp[i - j]. The recurrence becomes dp[i] = max(dp[i], j * (i - j), j * dp[i - j]). This ensures every partition combination is considered while reusing previously computed results. The nested iteration leads to O(n2) time complexity and O(n) space.
Approach 2: Mathematical Greedy Insight (O(1) time, O(1) space)
The optimal solution comes from a key observation in math: splitting numbers into as many 3s as possible produces the maximum product. For example, 10 = 3 + 3 + 4 gives product 36, which is larger than other splits like 5 + 5. The reason is that 3 provides the best multiplicative growth compared to larger segments. Special cases occur when the remainder becomes 1; instead of 3 + 1, convert it into 2 + 2 because 2 × 2 is larger than 3 × 1. The algorithm repeatedly subtracts 3 from n and multiplies the result until the remaining value is ≤ 4, then multiplies the remainder. This produces the optimal product in constant time and space.
Recommended for interviews: The dynamic programming solution demonstrates strong problem-solving fundamentals and is the approach most candidates derive during interviews. It clearly shows how subproblems combine to form the optimal answer. The mathematical approach is the true optimal solution and often appears as a follow-up optimization once you recognize the pattern that breaking numbers into 3s maximizes the product.
Approach 1: 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.
This C code defines a dynamic programming approach to solving the integer break problem. We initialize an array dp, where dp[i] is the maximum product obtainable for integer i. A nested loop calculates the maximum product for each integer by checking the product of all possible splits (j * (i-j) and j * dp[i-j]).
Complexity
Time Complexity: O(n^2) because of the nested loop iterating through i and j.
Space Complexity: O(n) for the dp array.
Approach 2: 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.
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.
Complexity
Time Complexity: O(log n), as we repeatedly subtract 3.
Space Complexity: O(1) since no extra space is used besides variables.
Approach 3: Dynamic Programming
We define f[i] as the maximum product that can be obtained by splitting the positive integer i, with an initial condition of f[1] = 1. The answer is f[n].
Consider the last number j split from i, where j \in [1, i). For the number j split from i, there are two cases:
- Split
iinto the sum ofi - jandj, without further splitting, where the product is(i - j) times j; - Split
iinto the sum ofi - jandj, and continue splitting, where the product isf[i - j] times j.
Therefore, we can derive the state transition equation:
$
f[i] = max(f[i], f[i - j] times j, (i - j) times j) \quad (j \in [0, i))
Finally, returning f[n] will suffice.
The time complexity is O(n^2), and the space complexity is O(n). Here, n$ is the given positive integer.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
C
Approach 4: Mathematics
When n < 4, since the problem requires splitting into at least two integers, n - 1 yields the maximum product. When n geq 4, we split into as many 3s as possible. If the last segment remaining is 4, we split it into 2 + 2 for the maximum product.
The time complexity is O(1), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) because of the nested loop iterating through |
| Mathematical Approach | Time Complexity: O(log n), as we repeatedly subtract 3. |
| Dynamic Programming | — |
| Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | Best for interviews when deriving the solution from first principles and demonstrating DP reasoning. |
| Mathematical Greedy | O(1) | O(1) | Use when you recognize the mathematical pattern that splitting into 3s maximizes product. |
Video Solution
Integer Break - Dynamic Programming - Leetcode 343 - Python • NeetCode • 41,297 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Integer Break easy or hard?
Integer Break Python/Java solution
How to solve Integer Break in O(1)?
What is the best approach for Integer Break?
Is Integer Break asked at Google/Amazon/Meta?
What data structure is used in Integer Break?
What is the time complexity of Integer Break?
Ready to solve this problem?
Practice Integer Break with our built-in code editor and test cases.
Practice on FleetCode