LeetCode 343: Integer Break

Problem Restatement

We are given an integer n.

We must break n into the sum of at least two positive integers.

Among all possible breaks, return the maximum product of those integers.

For example:

10 = 3 + 3 + 4

The product is:

3 * 3 * 4 = 36

So for n = 10, the answer is 36.

The constraints are:

2 <= n <= 58

The problem statement asks to break n into k positive integers where k >= 2, then maximize the product.

Input and Output

Function shape:

def integerBreak(n: int) -> int:
    ...

Examples

Example 1:

Input: n = 2
Output: 1

Explanation:

2 = 1 + 1
1 * 1 = 1

Example 2:

Input: n = 10
Output: 36

Explanation:

10 = 3 + 3 + 4
3 * 3 * 4 = 36

First Thought: Try Every Break

A direct recursive idea is:

For every possible first part x, recursively solve the remaining value n - x.

But there is a detail.

After we split n into:

x + (n - x)

we have two choices for the second part:

1. Keep n - x as one number.
2. Break n - x further.

So the best product for this split is:

x * max(n - x, best product after breaking n - x)

This naturally leads to dynamic programming.

Key Insight

Let:

dp[i] = maximum product obtainable by breaking integer i

For each i, try every first part x from 1 to i - 1.

The remaining part is:

i - x

For that remaining part, we choose the better of:

So the transition is:

dp[i] = max(dp[i], x * (i - x), x * dp[i - x])

This works because the original number must be broken at least once, but after that, each remaining part may or may not be broken further.

Algorithm

Create an array dp of length n + 1.

Set:

dp[1] = 1

Then for every i from 2 to n:

1. Try every split x + (i - x).
2. Compare:
   1. x * (i - x)
   2. x * dp[i - x]
3. Store the best value in dp[i].

Return:

dp[n]

Walkthrough

Use:

n = 10

Some important values:

dp[2] = 1      from 1 + 1
dp[3] = 2      from 1 + 2
dp[4] = 4      from 2 + 2
dp[5] = 6      from 2 + 3
dp[6] = 9      from 3 + 3
dp[7] = 12     from 3 + 4
dp[8] = 18     from 3 + 3 + 2
dp[9] = 27     from 3 + 3 + 3
dp[10] = 36    from 3 + 3 + 4

For i = 10, one split is:

3 + 7

If we do not break 7, product is:

3 * 7 = 21

If we break 7 optimally:

dp[7] = 12

then product is:

3 * 12 = 36

So dp[10] becomes 36.

Correctness

The algorithm considers every possible first split of each integer i.

For a fixed split:

i = x + (i - x)

there are exactly two relevant choices for the second part.

It can remain whole, giving:

x * (i - x)

or it can be broken further, giving:

x * dp[i - x]

The value dp[i - x] is already correct because i - x < i, and the table is filled from smaller values to larger values.

Taking the maximum over all first parts x therefore considers every valid way to break i.

The base value handles the smallest subproblem.

Since dp[n] is computed from all valid breaks of n, it equals the maximum product obtainable after breaking n into at least two positive integers.

Complexity

Given n <= 58, this is easily fast enough.

Implementation

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1

        for total in range(2, n + 1):
            for first in range(1, total):
                rest = total - first

                dp[total] = max(
                    dp[total],
                    first * rest,
                    first * dp[rest],
                )

        return dp[n]

Code Explanation

Create the DP table:

dp = [0] * (n + 1)

Set the smallest useful value:

dp[1] = 1

Now compute products for each total:

for total in range(2, n + 1):

Try every possible first number:

for first in range(1, total):

The remaining number is:

rest = total - first

Then compare the two choices:

first * rest

means we stop splitting the remaining part.

first * dp[rest]

means we split the remaining part optimally.

The best value is stored in:

dp[total]

Greedy Math Version

There is also a shorter mathematical solution.

For maximum product, we want to use as many 3s as possible, except when the remainder would be 1.

Why?

For values larger than 4, splitting off a 3 improves or preserves the product.

But a remainder of 1 is bad because:

3 * 1 < 2 * 2

So if the remainder is 1, replace one 3 + 1 with 2 + 2.

Implementation:

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

This version runs in O(n) time with the loop, or O(1) if written with exponentiation.

Testing

def run_tests():
    s = Solution()

    assert s.integerBreak(2) == 1
    assert s.integerBreak(3) == 2
    assert s.integerBreak(4) == 4
    assert s.integerBreak(5) == 6
    assert s.integerBreak(6) == 9
    assert s.integerBreak(10) == 36
    assert s.integerBreak(12) == 81
    assert s.integerBreak(58) == 1549681956

    print("all tests passed")

run_tests()

Test meaning: