343. Integer Break - Explanation

Description

You are 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 = 4

Output: 4

Explanation: 4 = 2 + 2, 2 x 2 = 4.

Example 2:

Input: n = 12

Output: 81

Explanation: 12 = 3 + 3 + 3 + 3, 3 x 3 x 3 x 3 = 81.

Constraints:

2 <= n <= 58

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion (Brute Force)

Intuition

To maximize the product, we can try all possible ways to split the integer. For each number, we consider breaking it into two parts and recursively computing the best product for each part. The key insight is that a subpart can either be broken further or kept as is, except for the original number which must be broken at least once.

Algorithm

Define a recursive function dfs(num) that returns the maximum product obtainable from num.
Base case: if num == 1, return 1.
If num equals the original input n, initialize result to 0 (must break). Otherwise, num itself is a valid option.
Try all splits i from 1 to num - 1, computing dfs(i) * dfs(num - i) and keeping the maximum.
Return the maximum product found.

class Solution:
    def integerBreak(self, n: int) -> int:
        def dfs(num):
            if num == 1:
                return 1
            res = 0 if num == n else num
            for i in range(1, num):
                val = dfs(i) * dfs(num - i)
                res = max(res, val)
            return res
        return dfs(n)

Time & Space Complexity

Time complexity: $O(n ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Recursion

Intuition

Instead of trying all pairs of splits, we can think of this as a bounded knapsack problem where we repeatedly subtract values from the number. We pick a value i (from 1 to n-1) and multiply it with the optimal product of the remaining. By allowing repeated use of the same value, we explore all combinations more efficiently.

Algorithm

Define dfs(num, i) where num is the remaining value and i is the maximum allowed factor.
Base case: if num or i is 0, return 1.
If i > num, reduce i to num.
Choose between:
- Using factor i: multiply i * dfs(num - i, i).
- Skipping factor i: call dfs(num, i - 1).
Return the maximum of these two choices.

class Solution:
    def integerBreak(self, n: int) -> int:
        def dfs(num, i):
            if min(num, i) == 0:
                return 1

            if i > num:
                return dfs(num, num)

            return max(i * dfs(num - i, i), dfs(num, i - 1))

        return dfs(n, n - 1)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ for recursion stack.

3. Dynamic Programming (Top-Down) - I

Intuition

The brute force recursion recalculates the same subproblems many times. By storing the results in a memoization table, we avoid redundant work. Each unique value of num is computed only once, then reused.

Algorithm

Create a hash map dp with base case dp[1] = 1.
Define dfs(num):
- If num is already in dp, return the cached value.
- Initialize dp[num] to 0 if num == n, else to num.
- For each split point i from 1 to num - 1, update dp[num] with max(dp[num], dfs(i) * dfs(num - i)).
- Return dp[num].
Call dfs(n) and return the result.

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = {1: 1}

        def dfs(num):
            if num in dp:
                return dp[num]

            dp[num] = 0 if num == n else num
            for i in range(1, num):
                val = dfs(i) * dfs(num - i)
                dp[num] = max(dp[num], val)
            return dp[num]

        return dfs(n)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Dynamic Programming (Top-Down) - II

Intuition

This memoizes the bounded knapsack formulation. We cache results based on both the remaining sum and the current maximum factor being considered. This avoids recomputing identical states across different recursion paths.

Algorithm

Create a 2D memo table dp[num][i] initialized to -1.
Define dfs(num, i):
- If min(num, i) == 0, return 1.
- If dp[num][i] is cached, return it.
- If i > num, set dp[num][i] = dfs(num, num).
- Otherwise, set dp[num][i] = max(i * dfs(num - i, i), dfs(num, i - 1)).
- Return dp[num][i].
Call dfs(n, n - 1) and return the result.

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = {}
        def dfs(num, i):
            if min(num, i) == 0:
                return 1
            if (num, i) in dp:
                return dp[(num, i)]
            if i > num:
                dp[(num, i)] = dfs(num, num)
                return dp[(num, i)]

            dp[(num, i)] = max(i * dfs(num - i, i), dfs(num, i - 1))
            return dp[(num, i)]

        return dfs(n, n - 1)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

5. Dynamic Programming (Bottom-Up)

Intuition

We can solve this iteratively by building up solutions from smaller numbers. For each number from 2 to n, we compute the best product by trying all ways to split it and combining previously computed results.

Algorithm

Create an array dp of size n + 1 with dp[1] = 1.
For each num from 2 to n:
- Initialize dp[num] to num (or 0 if num == n).
- For each i from 1 to num - 1, update dp[num] = max(dp[num], dp[i] * dp[num - i]).
Return dp[n].

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

        for num in range(2, n + 1):
            dp[num] = 0 if num == n else num
            for i in range(1, num):
                dp[num] = max(dp[num], dp[i] * dp[num - i])

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

6. Math

Intuition

A mathematical analysis reveals that the optimal strategy is to break the number into as many 3s as possible. This is because 3 maximizes the product per unit. We avoid leaving a remainder of 1 since 3 + 1 = 4 and 2 * 2 > 3 * 1. For small values (n <= 3), we handle them as special cases.

Algorithm

If n <= 3, return n - 1 (since we must break at least once).
Repeatedly subtract 3 from n and multiply the result by 3, until n <= 4.
Multiply the final remainder (which will be 2, 3, or 4) into the result.
Return the result.

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1

        res = 1
        while n > 4:
            res *= 3
            n -= 3
        return res * n

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

7. Math (Optimal)

Intuition

We can compute the result directly using the count of 3s. If n % 3 == 0, the answer is 3^(n/3). If n % 3 == 1, we should use one fewer 3 and multiply by 4 instead (since 2 * 2 > 3 * 1). If n % 3 == 2, we multiply the power of 3 by 2.

Algorithm

If n <= 3, return n - 1.
Compute res = 3^(n / 3).
If n % 3 == 1, return (res / 3) * 4.
If n % 3 == 0, return res.
Otherwise, return res * 2.

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1

        res = 3 ** (n // 3)
        if n % 3 == 1:
            return (res // 3) * 4

        return res * max(1, (n % 3))

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting the Original Number Must Be Broken

A common mistake is allowing the original input n to remain unbroken. The problem requires at least one split, so returning n itself is invalid. For example, integerBreak(4) must return 4 (from 2 * 2), not 4 unchanged. Ensure your base case or initialization forces at least one break for the original number while still allowing subproblems to use values directly.

Mishandling Small Values of n

The cases n = 2 and n = 3 are special because breaking them actually produces a smaller product than keeping them whole (for subproblems). For n = 2, breaking gives 1 * 1 = 1 but we must return 1 since we must break. For n = 3, breaking gives at best 1 * 2 = 2. Many solutions fail by not treating these edge cases differently from the general recursive case.

Using Factors of 1 or Factors Greater Than 4

Breaking off a factor of 1 never helps since 1 * (n-1) < n. Similarly, keeping any factor greater than 4 is suboptimal because it can always be split into smaller factors with a larger product. For example, 5 should be split into 2 + 3 giving 6 rather than kept as 5. The optimal solution primarily uses factors of 2 and 3.