Integer Break — Solution in Python, Java & C++
Integer Break solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Integer Break is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, break it into the sum of at least two positive integers and maximise the product of those integers.
Return the maximum product you can obtain.
Example 1
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, so the product is 1.
Example 2
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4.
Example 3
Input: n = 4
Output: 4
Explanation: 4 = 2 + 2.
Constraints
2 <= n <= 40
Hints for Integer Break
Hint 1
For each first piece
k, you may either stop there — productk × (n - k)— or break the remainder further, givingk × dp[n - k].Hint 2
Take the larger of those two for every
k, and the maximum over allk.Hint 3
The greedy answer uses as many 3s as possible, which the DP will reproduce.
How to solve Integer Break
For each first piece k, either stop (k · (n-k)) or keep breaking the remainder (k · dp[n-k]); take the best over all k.
Approach
- Set
dp[1] = 1. - For
ifrom 2 tonandkfrom 1 toi-1,dp[i] = max(dp[i], k·(i-k), k·dp[i-k]). - Return
dp[n].
Why it works
dp[i] is the best product of a break into at least two parts; allowing "stop after one split" separately is what handles the at-least-two rule at the top level while still letting sub-breaks use a single piece.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- The greedy answer uses as many 3s as possible (with a 4 or 2 at the end) — the DP reproduces it and is easier to justify.
Reference solution
Python
def integerBreak(n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for k in range(1, i):
dp[i] = max(dp[i], k * (i - k), k * dp[i - k])
return dp[n]Java
public static int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k < i; k++) {
dp[i] = Math.max(dp[i], Math.max(k * (i - k), k * dp[i - k]));
}
}
return dp[n];
}C++
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k < i; k++) {
dp[i] = max(dp[i], max(k * (i - k), k * dp[i - k]));
}
}
return dp[n];
}JavaScript
var integerBreak = function(n) {
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
for (let k = 1; k < i; k++) {
const candidate = Math.max(k * (i - k), k * dp[i - k]);
if (candidate > dp[i]) dp[i] = candidate;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming