Integer Break

Difficulty: Medium Source: NeetCode

Problem

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.

Example 1: Input: n = 2 Output: 1 (2 = 1 + 1, product = 1)

Example 2: Input: n = 10 Output: 36 (10 = 3 + 3 + 4, product = 36)

Constraints:

• 2 <= n <= 58

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dynamic Programming — optimal substructure
• Math Intuition — understanding why breaking into 3s is optimal

1. Brute Force (Recursion with Memoization)

Intuition

At each step, try splitting off each possible first piece k (from 1 to n-1). The remaining n-k can either be left as-is (if we want n-k as one piece) or recursively split further. Take the maximum of k * (n-k) and k * dp(n-k).

Algorithm

1. dp(n) = max product from breaking n into at least 2 pieces.
2. For each split k from 1 to n-1:
   • product = k * max(n - k, dp(n - k)).
3. Return max over all k.

Solution

def integerBreak_memo(n):
    memo = {}

    def dp(num):
        if num in memo:
            return memo[num]
        if num == 1:
            return 1

        best = 0
        for k in range(1, num):
            # k is one piece; (num - k) can be kept whole or broken further
            product = k * max(num - k, dp(num - k))
            best = max(best, product)

        memo[num] = best
        return best

    return dp(n)


print(integerBreak_memo(2))   # 1
print(integerBreak_memo(3))   # 2
print(integerBreak_memo(4))   # 4
print(integerBreak_memo(10))  # 36
print(integerBreak_memo(58))  # 1549681956

Complexity

• Time: O(n²) with memoization
• Space: O(n) — memo table

2. Dynamic Programming (Bottom-Up)

Intuition

Build dp[i] = maximum product from breaking i. For each number, try all first-piece sizes j and check both keeping (i-j) whole and splitting it: dp[i] = max(j * (i-j), j * dp[i-j]).

Math insight (worth knowing): The optimal strategy is to break everything into 3s. You never want a piece of size 1 (it doesn’t contribute to the product), and splitting any piece ≥ 5 into smaller pieces always gives a better product. Remainders: if remainder is 0 → all 3s; if 1 → replace one 3+1 with two 2s; if 2 → add one 2.

Algorithm

1. Initialize dp = [0] * (n + 1), dp[1] = 1.
2. For each i from 2 to n:
   • For each j from 1 to i-1:
     • dp[i] = max(dp[i], j * (i - j), j * dp[i - j]).
3. Return dp[n].

Solution

def integerBreak(n):
    dp = [0] * (n + 1)
    dp[1] = 1  # not really used, but set for completeness

    for i in range(2, n + 1):
        for j in range(1, i):
            # Either keep (i-j) as one piece, or break it further
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j])

    return dp[n]


def integerBreak_math(n):
    """O(1) math solution using the 'break into 3s' insight."""
    if n == 2:
        return 1
    if n == 3:
        return 2
    threes = n // 3
    remainder = n % 3
    if remainder == 0:
        return 3 ** threes
    elif remainder == 1:
        # Replace one 3 with two 2s: 3*1 → 2*2 = 4 > 3
        return 3 ** (threes - 1) * 4
    else:  # remainder == 2
        return 3 ** threes * 2


print(integerBreak(2))   # 1
print(integerBreak(3))   # 2
print(integerBreak(4))   # 4
print(integerBreak(10))  # 36
print(integerBreak(58))  # 1549681956

print(integerBreak_math(2))   # 1
print(integerBreak_math(10))  # 36
print(integerBreak_math(58))  # 1549681956

Complexity

• Time: O(n²) for DP; O(1) for math solution
• Space: O(n) for DP; O(1) for math

Common Pitfalls

Forgetting the constraint of at least 2 pieces. You must split n into at least 2 parts. So dp[2] = 1*1 = 1, not 2.

Not considering keeping (i-j) as a whole piece. When building dp[i], you should consider both j * (i-j) (two pieces: j and i-j) and j * dp[i-j] (j as one piece, then optimally split i-j). Missing the j * (i-j) option causes wrong answers for small n.

Using the math shortcut without verifying n=2 and n=3. For n=2: only split is 1+1, product=1. For n=3: splits are 1+2 or 1+1+1, best is 1*2=2. These are special cases that the formula handles by the remainder logic.