Integer Break
Given an integer n, break it into the sum of at least two positive integers and maximize the product of those integers.
- 2 <= n <= 58
Intuition
Integer break splits an integer into at least two positive parts and maximises their product. The DP formulation is the general answer, and there is a mathematical shortcut worth knowing.
The DP asks, for each value up to n, what the best product is:
- dp[i] = max over j of max(j, dp[j]) × max(i − j, dp[i − j]).
The max(j, dp[j]) term is the part usually missed. Each piece can either be left whole as j or broken further into dp[j], whichever is larger. Using only dp[j] forces every piece to be broken, which is wrong — dp[2] is 1, since 2 must split into 1+1, yet keeping 2 whole is often better.
The mathematical route explains why: the optimum uses as many 3s as possible. Splitting into equal parts of size e is theoretically best, and 3 is the nearest integer, beating 2 because 3 × 3 = 9 exceeds 2 × 2 × 2 = 8 for the same total of 6.
The remainder decides the tail. If n % 3 == 0, use all 3s. If the remainder is 1, replace one 3 with two 2s — 2 × 2 = 4 beats 3 × 1 = 3. If the remainder is 2, one 2 joins the 3s.
The base cases are exceptions to that rule: n = 2 gives 1 and n = 3 gives 2, because the problem requires at least two parts even when leaving the number whole would be larger.
The DP is O(n²), the mathematical version O(1) after the constant-time remainder check.
When a problem asks you to split an integer into parts that maximise (or minimise) a product, the answer almost always involves a specific small factor used repeatedly. The key is to test which small factor (2 or 3) wins and handle the remainder. The 'break into 3s' pattern also appears in problems about cutting rope or splitting numbers for maximum product.
Approach
Before reading on: price up what the brute force costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(1) time and O(1) space.
Define the DP state
dp[i] is the maximum product obtainable from i. Each value is built from every way of splitting it into two parts.
Allow pieces to stay whole
Use max(j, dp[j]) for each piece — either keep it whole or break it further. Using only dp[j] forces a split, and dp[2] = 1 shows why that loses.
Handle the required split
n = 2 returns 1 and n = 3 returns 2, since at least two parts are mandatory even though leaving the number whole would be larger.
Know the mathematical shortcut
The optimum uses as many 3s as possible. Equal parts near size e are best, and 3 beats 2 because 3 × 3 = 9 exceeds 2 × 2 × 2 = 8.
Handle the remainder of one
When n % 3 == 1, replace one 3 with two 2s — 2 × 2 = 4 beats 3 × 1 = 3. A remainder of 2 simply adds one 2.
Cost of each approach
The DP is O(n²) time with O(n) space; the mathematical version is O(1) after a constant-time remainder check, or O(log n) with fast exponentiation.
Solution & live demo
Common pitfalls
Not handling remainder 1 — leaving a factor of 1 in the product
return 3 ** (n // 3) * (n % 3)
if n % 3 == 1:
return 3 ** (n // 3 - 1) * 4
return 3 ** (n // 3) * (n % 3 if n % 3 else 1)When n % 3 == 1, the formula gives 3^k **1, which wastes a factor. Pulling back one 3 and using 4 = 2** 2 instead turns 3 * 1 = 3 into 4, a strict improvement.
Returning n for small values instead of respecting the split constraint
if n <= 3:
return nif n == 2:
return 1
if n == 3:
return 2The problem requires at least two parts. n = 3 unsplit is 3, but the required split gives 1 + 2 = 2. Returning n directly violates the constraint.
Using 2s instead of 3s for the main decomposition
return 2 ** (n // 2)
return 3 ** (n // 3) * ...
For n = 6, using 2s gives 2 2 2 = 8, but using 3s gives 3 * 3 = 9. Three 2s always loses to two 3s for the same sum, so 3 should be the primary factor.
Edge cases
n = 2Only split is 1 + 1. Return 1.
n = 3Best split is 1 + 2. Return 2. Note: 3 itself is better as a factor when it appears inside a larger split, but the 'at least two' rule prevents returning 3.
n = 4Split is 2 + 2, product = 4. Equivalently, 4 itself equals 2 **2. The remainder-1 branch computes 3^0** 4 = 4, which is correct.