Integer Break
Given an integer n, break it into the sum of at least two positive integers and maximize the product of those integers.
Intuition
The mathematical insight is that 3 is the magic number. Any integer greater than 4 should be broken into 3s as much as possible. Why? Because 3 3 = 9 > 2 2 2 = 8 (three 2s is worse than two 3s for the same sum of 6), and any factor >= 5 can always be broken further to increase the product (5 < 2 3). The only exception is when the remainder after dividing by 3 is 1 — then pulling back one 3 and using two 2s instead gives 2 2 = 4 > 1 3 = 3. For small n (2 and 3), the constraint 'at least two parts' forces a suboptimal split.
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
Handle the small cases directly
For n = 2, the only split is 1 + 1, product = 1. For n = 3, the best is 1 + 2, product = 2. These are forced by the 'at least two parts' rule — you cannot just return n itself. For n >= 4, the general strategy kicks in.
Extract as many 3s as possible, adjusting the remainder
Divide n by 3. If the remainder is 0, the answer is 3^(n/3). If the remainder is 1, pull back one 3 and combine it with the 1 to form two 2s — so the answer is 3^(n/3 - 1) 4. If the remainder is 2, just multiply the 2 onto the 3s — the answer is 3^(n/3) 2.
Why 3 is optimal and 1 is never used
A factor of 1 contributes nothing to the product, so it is never optimal. A factor of 4 equals 2 2, so it does not help over two 2s. A factor >= 5 can be split into 3 + (k-3) where 3 (k-3) > k for k >= 5. Among small factors, 3 3 = 9 > 2 2 * 2 = 8 for a sum of 6, making 3 strictly better than 2 when you have three or more 2s. The entire argument boils down to: use 3s, and fix the remainder. O(1) time and space.
Solution
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.