Integer Break
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 get.
Input
A single integer n.
Output
An integer: the largest product obtainable after breaking n into at least two positive parts.
Constraints
- •
2 <= n <= 58
Examples
Example 1
n = 2
1Example 2
n = 10
36Example 3
n = 8
18Learning Objectives
- Define a max-product DP while respecting the requirement to make at least one cut.
- Derive the transition by choosing the first piece and deciding what to do with the remainder.
- Explain why the recurrence compares breaking the remainder with leaving it whole.
- Recognise integer partition problems as decision DP over cut positions.
Intuition
The first cut separates i into a first piece j and a remainder i - j. That cut is mandatory because the problem requires at least two positive integers.
After making that cut, the remainder presents a choice. Sometimes the best product leaves it whole, such as 2 + 2 for i = 4. Other times the best product breaks it further, such as taking 3 and then optimally breaking 7 when solving i = 10.
That is why the recurrence must compare both options: j * (i - j) for stopping after the current cut, and j * dp[i - j] for continuing to break the remainder.
Common mistakes
- ×Using only **j * dp[i - j]** and forgetting the option to leave the remainder unbroken.
- ×Returning **n** for small values, which violates the requirement to break the integer at least once.
- ×Trying to use **dp[0]** as a meaningful product state; the transition only needs positive remainders.
- ×Counting different orders of the same pieces as separate choices, even though only the maximum product matters.
- ×Stopping the inner loop too early without proving symmetry; the full **1..i - 1** loop is easiest and safe.
State Definition
Let dp[i] be the maximum product obtainable by breaking integer i into at least two positive integers. The answer is dp[n].
State Transition
Choose the first piece j, where 1 <= j < i. The remainder is i - j. Once this first cut has been made, there are two valid choices for the remainder:
- Stop breaking it: product j * (i - j).
- Break it further using the best known value: product j * dp[i - j].
So the recurrence is:
dp[i] = max over 1 <= j < i of max(j * (i - j), j * dp[i - j])
The base dp[1] = 0 means 1 cannot be broken into two positive parts. Values from 2 upward are computed from smaller remainders.
Solutions
Solution: Bottom-up max-product DP
Use this to demonstrate the decision clearly. The mathematical greedy solution is shorter, but the DP recurrence is the best way to explain why breaking or preserving the remainder must both be considered.
Compute dp[total] for increasing totals. For every possible first piece, evaluate the product if the remainder stays whole and the product if the remainder is broken according to dp. The larger of those two is the best product for that first piece, and the maximum across first pieces becomes dp[total].
Step-by-step
- Create an integer array dp of size n + 1. The default dp[1] = 0 is correct because 1 cannot be broken.
- For each total from 2 through n, initialise a local best product.
- Try every first piece first from 1 to total - 1.
- Compare first * remainder with first * dp[remainder] to decide whether the remainder should stay whole or be broken further.
- Store the best product for this total, then return dp[n].
O(n²)
O(n)
Every total tries all possible first cuts, and the table stores one best product per total.
Java implementation
Dry Run
Sample input
n = 10. Track the best product for each total after considering all first cuts.
| total | best decision | dp[total] | why |
|---|---|---|---|
| 2 | 1 + 1 | 1 | Only one valid cut exists. |
| 3 | 1 + 2 | 2 | Leaving the remainder whole gives 1 * 2. |
| 4 | 2 + 2 | 4 | Stopping at 2 * 2 beats breaking a remainder into 1s. |
| 5 | 2 + 3 | 6 | Stopping at 2 * 3 is best. |
| 6 | 3 + 3 | 9 | Stopping at 3 * 3 is best. |
| 7 | 3 + 4 | 12 | The best product is 3 * 4, also reachable by breaking 4 as 2 + 2. |
| 8 | 3 + break 5 | 18 | 3 * dp[5] = 18 beats 3 * 5 = 15. |
| 9 | 3 + break 6 | 27 | 3 * dp[6] uses 3 + 3 + 3. |
| 10 | 3 + break 7 | 36 | 3 * dp[7] gives 3 + 3 + 4. |
The answer for n = 10 is dp[10] = 36. The critical step is allowing the remainder 7 to be broken further instead of multiplying by 7 directly.
Complexity Analysis
The DP table is small for the given constraints, and the nested cut loop makes the break-or-not-break choice explicit for every integer.
Bottom-up max-product DP
O(n²)
O(n)
Every total tries all possible first cuts, and the table stores one best product per total.
Interview Tips
Emphasise the phrase at least two positive integers. That requirement is exactly why dp[i] means the best product after a break, not the best product where choosing i itself is allowed. Then call out the key comparison: leave the remainder whole or replace it with its best broken product.
Likely follow-ups
- Can you derive the O(1) greedy solution based on using as many 3s as possible?
- How would you return the actual parts that produce the maximum product?
- What changes if exactly **k** parts are required?
- How would the recurrence change if each part had to belong to a given allowed set?
Similar Problems
Key Takeaways
- Integer Break requires at least one cut, so **dp[i]** should represent a broken integer, not the option to keep **i** whole.
- After the first cut, the remainder may be better left whole or broken further.
- The recurrence maximises over all first pieces **j** and both remainder choices.
- Decision DP can optimise a value, not only answer reachable or unreachable.