LeetCode 343 - Integer Break

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to split a positive integer n into the sum of at least two positive integers, then maximize the product of those integers.

In other words, we are not allowed to keep the number as-is. We must break it into multiple parts, and among all possible valid splits, we want the one whose multiplication result is the largest.

For example, if n = 10, some possible decompositions are:

5 + 5, product = 25
6 + 4, product = 24
3 + 3 + 4, product = 36
2 + 2 + 2 + 2 + 2, product = 32

The maximum possible product is 36, so the answer is 36.

The input consists of a single integer n, where:

2 <= n <= 58

The output is a single integer representing the maximum product obtainable after splitting n into at least two positive integers.

The constraint upper bound of 58 is relatively small, which means even a dynamic programming solution with quadratic complexity is completely acceptable. However, the problem also has a strong mathematical pattern that allows for an even cleaner solution.

Several edge cases are important immediately:

n = 2 is the smallest valid input. Since we must split it, the only option is 1 + 1, giving a product of 1.
n = 3 is tricky because although 3 itself is larger than 2, we are forced to split it. The best split is 2 + 1, producing 2.
Small numbers often behave differently from larger ones because the forced split constraint changes the optimal strategy.
A naive greedy approach can fail if we do not carefully handle remainders such as 4.

Approaches

Brute Force Approach

The brute-force solution tries every possible way to split the integer into sums of positive integers, computes the product for each decomposition, and returns the maximum.

For example, for n = 5, brute force would explore:

1 + 4
2 + 3
1 + 1 + 3
1 + 2 + 2
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1

For every partition, we compute the multiplication result and keep the best value.

This approach is correct because it examines every possible valid decomposition. Since the optimal answer must appear among all possible partitions, exhaustive search guarantees correctness.

However, the number of integer partitions grows exponentially. Recomputing subproblems repeatedly makes the brute-force recursion extremely inefficient for larger inputs.

Optimal Approach, Mathematical Greedy Insight

The key observation is that breaking a number into pieces of size 3 produces the largest product.

This comes from comparing multiplication results:

Splitting into 2 + 2 gives 4
Splitting into 3 + 3 gives 9
Splitting into larger numbers is usually worse because:

4 = 2 × 2
5 < 3 × 2
6 = 3 × 3

Mathematically, repeatedly using 3 maximizes the product.

There is one important exception:

We should never leave a remainder of 1
Instead of 3 + 1, we use 2 + 2

For example:

10 = 3 + 3 + 4
36 = 3 × 3 × 4

This is better than:

10 = 3 + 3 + 3 + 1
27 = 3 × 3 × 3 × 1

So the optimal strategy becomes:

Repeatedly take 3
If the remainder becomes 4, stop and use 4
Handle 2 and 3 as special base cases

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores all integer partitions recursively
Optimal	O(n)	O(1)	Uses the mathematical property that 3s maximize the product

Algorithm Walkthrough

Optimal Greedy Algorithm

Handle the smallest special cases first.

If n = 2, the answer is 1 because the only split is 1 + 1.

If n = 3, the answer is 2 because the best split is 2 + 1.

These cases are special because the problem requires at least one split. 2. Initialize a variable to store the running product.

We start with:

product = 1

Repeatedly remove groups of 3.

While n > 4, multiply the product by 3 and reduce n by 3.

We stop at 4 because:

4 = 2 × 2

which is better than:

3 × 1

Multiply the remaining value into the product.

After repeatedly removing 3s, the remaining n will be either:

Each of these should be multiplied directly into the result. 5. Return the final product.

Why it works

The mathematical proof relies on the fact that splitting numbers larger than 4 increases the product, and among all possible splits, using 3 gives the best multiplicative growth.

For any integer x >= 5:

3 × (x - 3) > x

So replacing a large number with a 3 and the remainder always improves the product.

The only exception occurs when a remainder of 1 appears, because multiplying by 1 does not help. Replacing 3 + 1 with 2 + 2 produces a larger product.

This guarantees that repeatedly extracting 3s leads to the optimal answer.

Python Solution

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        
        if n == 3:
            return 2
        
        product = 1
        
        while n > 4:
            product *= 3
            n -= 3
        
        return product * n

The implementation begins by handling the special cases 2 and 3. These must be treated separately because the problem requires at least one split.

The variable product stores the running multiplication result.

The while loop repeatedly removes groups of 3 from n. Each time we remove a 3, we multiply the running product by 3.

The loop stops once n <= 4. At this point, the remaining value is multiplied directly into the answer. This correctly handles the important 4 = 2 + 2 case.

The implementation is compact because the mathematical insight eliminates the need for recursion or dynamic programming tables.

Go Solution

func integerBreak(n int) int {
    if n == 2 {
        return 1
    }

    if n == 3 {
        return 2
    }

    product := 1

    for n > 4 {
        product *= 3
        n -= 3
    }

    return product * n
}

The Go implementation follows the exact same logic as the Python version.

Since the constraints are small, integer overflow is not a concern in Go. The maximum answer for n <= 58 fits safely inside a standard int.

Go uses a for loop instead of Python's while, but the behavior is identical.

Worked Examples

Example 1

Input: n = 2

Since n = 2 is a special case:

2 = 1 + 1
1 × 1 = 1

The algorithm immediately returns 1.

Step	n	product	Action
Initial	2	1	Special case
Return	2	1	Return 1

Final answer:

Example 2

Input: n = 10

Initial state:

n = 10
product = 1

Iteration 1

Since n > 4:

product = 1 × 3 = 3
n = 10 - 3 = 7

Iteration 2

Again, n > 4:

product = 3 × 3 = 9
n = 7 - 3 = 4

Now n = 4, so we stop the loop.

Final multiplication:

answer = 9 × 4 = 36

Step	n	product	Explanation
Initial	10	1	Start
After first 3	7	3	Extract a 3
After second 3	4	9	Extract another 3
Final	4	36	Multiply remaining 4

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The loop subtracts 3 each iteration
Space	O(1)	Only a few variables are used

Although the algorithm repeatedly subtracts 3, the number of iterations is very small because n <= 58. The runtime is linear in the value of n, and no additional data structures are allocated.

Test Cases

solution = Solution()

assert solution.integerBreak(2) == 1   # smallest valid input
assert solution.integerBreak(3) == 2   # special case requiring split
assert solution.integerBreak(4) == 4   # 2 + 2
assert solution.integerBreak(5) == 6   # 3 + 2
assert solution.integerBreak(6) == 9   # 3 + 3
assert solution.integerBreak(7) == 12  # 3 + 4
assert solution.integerBreak(8) == 18  # 3 + 3 + 2
assert solution.integerBreak(9) == 27  # all 3s
assert solution.integerBreak(10) == 36 # example from problem statement
assert solution.integerBreak(11) == 54 # 3 + 3 + 3 + 2
assert solution.integerBreak(12) == 81 # 3 + 3 + 3 + 3
assert solution.integerBreak(58) == 1549681956 # largest constraint

Test	Why
`n = 2`	Smallest valid input
`n = 3`	Special forced-split case
`n = 4`	Validates avoiding `3 + 1`
`n = 5`	Simple mixed decomposition
`n = 6`	Pure 3-based split
`n = 7`	Tests remainder handling
`n = 8`	Multiple greedy iterations
`n = 9`	All 3s case
`n = 10`	Official example
`n = 11`	Combination of 3s and 2
`n = 12`	Multiple optimal 3s
`n = 58`	Maximum constraint stress test

Edge Cases

Edge Case 1, `n = 2`

This is the smallest valid input and often causes bugs because the problem requires at least one split. A careless implementation might incorrectly return 2 instead of 1.

The implementation explicitly checks for n == 2 and returns 1.

Edge Case 2, Remainder of `1`

A naive greedy strategy that always extracts 3 can fail when the remaining value becomes 1.