Integer Break
Medium · Dynamic Programming · Math · Dynamic Programming
Problem
Given an integer n, write it as the sum of at least two positive integers.
Return the largest product those integers can have.
Examples
Input: n = 6 Output: 9
6 = 3 + 3 and 3 · 3 = 9.
Input: n = 2 Output: 1
The only split is 1 + 1.
Input: n = 11 Output: 54
11 = 3 + 3 + 3 + 2 gives 54.
Constraints
- 2 <= n <= 58
Approaches
- Baseline: DP over the first part — time O(n²), space O(n)
Follow-up
For large n (say up to 10^9) the answer is 3^(n // 3), adjusted for the remainder, and only needs fast exponentiation modulo a prime: O(log n). If the parts must be distinct, threes cannot repeat, and the best split looks like a run of consecutive numbers starting at 2; a table over sums that uses each part size at most once finds it exactly.
Related problems
Start free on Cariara · Coding problems · System design studio
