Integer Break

Description

Given a positive integer n, your task is to break it into the sum of at least two positive integers and maximize the product of those integers.

More precisely, you must find positive integers k₁, k₂, ..., kₘ (where m ≥ 2) such that k₁ + k₂ + ... + kₘ = n and the product k₁ × k₂ × ... × kₘ is as large as possible.

Return the maximum product you can achieve.

For instance, the number 10 can be broken in many ways: 2 + 8 (product 16), 3 + 7 (product 21), 3 + 3 + 4 (product 36), and so on. Among all possible decompositions, the one yielding the highest product is the answer.

Examples

Example 1

Input: n = 2

Output: 1

Explanation: The only way to break 2 into at least two positive integers is 1 + 1. The product is 1 × 1 = 1. There is no other decomposition since both parts must be positive.

Example 2

Input: n = 10

Output: 36

Explanation: The decomposition 10 = 3 + 3 + 4 gives a product of 3 × 3 × 4 = 36. Other decompositions like 2 + 2 + 3 + 3 give 2 × 2 × 3 × 3 = 36 as well, but no decomposition exceeds 36. Notably, 5 + 5 gives only 25, and 2 + 8 gives only 16.

Example 3

Input: n = 6

Output: 9

Explanation: The decomposition 6 = 3 + 3 gives a product of 3 × 3 = 9. Alternatives like 2 + 4 give 8, and 2 + 2 + 2 gives 8 as well. Splitting into 3 + 3 is optimal.

Constraints

2 ≤ n ≤ 58

Editorial

Brute Force

Intuition

The most natural way to think about this problem is to try every possible way of splitting the number. Imagine you have a rope of length n and you need to cut it into at least two pieces to maximize the product of the piece lengths.

For a number n, you can make a first cut at position 1, 2, 3, ..., up to n-1. After making a cut at position j, you get two pieces: one of length j and another of length n-j. Now for the piece of length n-j, you have a choice: keep it whole, or recursively break it further to get an even larger product.

This leads to a recursive approach: for each possible first cut at position j (from 1 to n-1), compute the maximum of either j × (n-j) — keeping the remainder intact — or j × maxProduct(n-j) — recursively breaking the remainder further. The answer is the maximum across all such choices.

However, this recursive exploration creates an exponential number of branches because the same subproblems (like computing maxProduct(3) or maxProduct(4)) get recomputed many times across different recursive paths.

Step-by-Step Explanation

Let's trace through with n = 6 using the recursive brute force:

Step 1: Call maxProduct(6). We try all first-cut positions j = 1, 2, 3, 4, 5.

Step 2: Try j=1: We get pieces 1 and 5.

Option A: 1 × 5 = 5 (keep 5 whole)
Option B: 1 × maxProduct(5) = 1 × 6 = 6 (break 5 further into 2+3)
Best for j=1: 6

Step 3: Try j=2: We get pieces 2 and 4.

Option A: 2 × 4 = 8 (keep 4 whole)
Option B: 2 × maxProduct(4) = 2 × 4 = 8 (break 4 into 2+2)
Best for j=2: 8

Step 4: Try j=3: We get pieces 3 and 3.

Option A: 3 × 3 = 9 (keep 3 whole)
Option B: 3 × maxProduct(3) = 3 × 2 = 6 (break 3 into 1+2)
Best for j=3: 9

Step 5: Try j=4: We get pieces 4 and 2.

Option A: 4 × 2 = 8 (keep 2 whole)
Option B: 4 × maxProduct(2) = 4 × 1 = 4 (break 2 into 1+1)
Best for j=4: 8

Step 6: Try j=5: We get pieces 5 and 1.

Option A: 5 × 1 = 5 (keep 1 whole)
Option B: 5 × maxProduct(1) = 5 × 0 = 0
Best for j=5: 5

Step 7: Overall maximum = max(6, 8, 9, 8, 5) = 9. Answer for n=6 is 9.

Integer Break — Recursive Exploration for n = 6 — Watch how the recursive brute force explores all possible ways to split 6, branching into subproblems that overlap extensively.

Algorithm

Define a recursive function maxProduct(n):
- Base case: if n ≤ 1, return 0
For each possible first cut position j from 1 to n-1:
- Compute two options:
  - Keep the remainder: j × (n - j)
  - Break the remainder further: j × maxProduct(n - j)
- Track the maximum across all options
Return the maximum product found

Code

class Solution {
public:
    int integerBreak(int n) {
        // Base case: cannot break 0 or 1 meaningfully
        if (n <= 1) return 0;
        
        int maxProduct = 0;
        for (int j = 1; j < n; j++) {
            // Option 1: keep (n-j) as is
            int keepWhole = j * (n - j);
            // Option 2: break (n-j) further recursively
            int breakFurther = j * integerBreak(n - j);
            maxProduct = max(maxProduct, max(keepWhole, breakFurther));
        }
        return maxProduct;
    }
};

class Solution:
    def integerBreak(self, n: int) -> int:
        # Base case: cannot break 0 or 1 meaningfully
        if n <= 1:
            return 0
        
        max_product = 0
        for j in range(1, n):
            # Option 1: keep (n-j) as is
            keep_whole = j * (n - j)
            # Option 2: break (n-j) further recursively
            break_further = j * self.integerBreak(n - j)
            max_product = max(max_product, keep_whole, break_further)
        
        return max_product

class Solution {
    public int integerBreak(int n) {
        // Base case: cannot break 0 or 1 meaningfully
        if (n <= 1) return 0;
        
        int maxProduct = 0;
        for (int j = 1; j < n; j++) {
            // Option 1: keep (n-j) as is
            int keepWhole = j * (n - j);
            // Option 2: break (n-j) further recursively
            int breakFurther = j * integerBreak(n - j);
            maxProduct = Math.max(maxProduct, Math.max(keepWhole, breakFurther));
        }
        return maxProduct;
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ)

Without memoization, the recursion branches exponentially. For each value of n, we try up to n-1 cuts, and each cut leads to a recursive call. The recursion tree has overlapping subproblems (e.g., maxProduct(3) is computed multiple times across different branches). The total number of unique calls is bounded by O(n), but without caching, each gets recomputed from scratch, leading to an exponential blowup.

Space Complexity: O(n)

The recursion depth is at most n (each recursive call reduces the argument by at least 1), so the call stack uses O(n) space.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2ⁿ) because it recomputes the same subproblems repeatedly. For example, maxProduct(3) is evaluated many times across different recursive branches when computing maxProduct(6) or larger values.

With n up to 58, an exponential approach would require on the order of 2⁵⁸ operations — far too many to complete within any reasonable time limit. Even maxProduct(30) would take billions of recursive calls without caching.

The key insight is that this problem has overlapping subproblems: the optimal product for a given integer depends only on that integer, regardless of how we arrived at it during recursion. This makes it a perfect candidate for dynamic programming, where we compute each subproblem exactly once and store the result for reuse.

Better Approach - Dynamic Programming

Intuition

Instead of recomputing results for the same subproblems, we can build a table bottom-up. We start by solving the smallest cases and work our way up to n.

Think of it like filling out a cheat sheet. If someone asked you 'what is the maximum product for the number 4?', you could look at your cheat sheet entries for 1, 2, and 3 — all of which you have already computed — and combine them to find the answer for 4.

We create an array dp where dp[i] represents the maximum product obtainable by breaking integer i. For each integer i from 2 to n, we try every possible first cut position j (from 1 to i-1). For each cut, we consider two options:

Keep the remainder whole: j × (i - j) — this treats i-j as a single piece
Break the remainder further: j × dp[i - j] — this uses the already-computed best product for i-j

We take the maximum across all cuts and both options. The crucial detail is that dp[i-j] represents the best product if we are forced to break i-j into at least two parts. Sometimes keeping i-j whole is better (for example, dp[3] = 2, but 3 itself is larger than 2), which is why we need both options.

Step-by-Step Explanation

Let's trace through with n = 10:

Step 1: Initialize dp array of size 11, all set to 1: dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].

Step 2: Compute dp[2]: Try j=1 → max(1×1, 1×dp[1]) = max(1, 1) = 1. dp[2] = 1.

Step 3: Compute dp[3]: Try j=1 → max(1×2, 1×1) = 2. Try j=2 → max(2×1, 2×1) = 2. dp[3] = 2.

Step 4: Compute dp[4]: Try j=1 → max(1×3, 1×2) = 3. Try j=2 → max(2×2, 2×1) = 4. Try j=3 → max(3×1, 3×1) = 3. dp[4] = 4.

Step 5: Compute dp[5]: Try j=2 → max(2×3, 2×2) = 6. Try j=3 → max(3×2, 3×2) = 6. dp[5] = 6.

Step 6: Compute dp[6]: Try j=3 → max(3×3, 3×2) = 9. dp[6] = 9.

Step 7: Compute dp[7]: Try j=3 → max(3×4, 3×4) = 12. dp[7] = 12.

Step 8: Compute dp[8]: Try j=3 → max(3×5, 3×6) = 18. dp[8] = 18.

Step 9: Compute dp[9]: Try j=3 → max(3×6, 3×9) = 27. dp[9] = 27.

Step 10: Compute dp[10]: Try j=3 → max(3×7, 3×12) = 36. Try j=4 → max(4×6, 4×9) = 36. dp[10] = 36.

Result: dp[10] = 36.

Integer Break — DP Table Construction for n = 10 — Watch how we fill the DP table bottom-up, using previously computed optimal products to build the answer for each new integer.

Algorithm

Create a dp array of size n+1, initialized to 1
For each integer i from 2 to n:
- For each possible cut position j from 1 to i-1:
  - Compute two options:
    - Keep remainder whole: j × (i - j)
    - Break remainder further: j × dp[i - j]
  - Update dp[i] = max(dp[i], both options)
Return dp[n]

Code

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // Option 1: keep (i-j) whole
                // Option 2: break (i-j) using previously computed dp
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n + 1)
        
        for i in range(2, n + 1):
            for j in range(1, i):
                # Option 1: keep (i-j) whole
                # Option 2: break (i-j) using previously computed dp
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        
        return dp[n]

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // Option 1: keep (i-j) whole
                // Option 2: break (i-j) using previously computed dp
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs from 2 to n (n-1 iterations). The inner loop runs from 1 to i-1 (up to n-1 iterations). Total operations: 1 + 2 + ... + (n-1) = n(n-1)/2, which simplifies to O(n²). With n ≤ 58, this is at most about 1,653 operations — very fast.

Space Complexity: O(n)

We use a single dp array of size n+1. No additional data structures that scale with input size.

Why This Approach Is Not Efficient

The dynamic programming approach runs in O(n²) time, which is perfectly acceptable for the constraint n ≤ 58. However, it does more work than necessary because it tries every possible cut position for each integer.

If you examine the DP table closely, a striking mathematical pattern emerges: the optimal splits overwhelmingly favor the number 3. For n ≥ 5, the best strategy is always to extract as many 3s as possible, with 2s filling in the remainder.

This is not a coincidence — it follows from a mathematical inequality: for any integer x ≥ 5, breaking x into smaller parts always yields a larger product. Furthermore, 3 × 3 = 9 > 2 × 2 × 2 = 8, so using 3s is more efficient than using 2s. And using 1 is never helpful since multiplying by 1 doesn't increase the product.

This mathematical insight lets us skip the inner loop entirely and compute the answer in O(1) time.

Optimal Approach - Greedy Mathematics

Intuition

The mathematical insight behind this problem is elegant. Let us reason about which numbers we should use in our decomposition:

Why never use 1: Multiplying by 1 adds nothing to the product. If we have a part equal to 1, we can always merge it with an adjacent part to get a strictly larger product. For example, 1 × 5 = 5 < 6 (just using 6 as one piece).

Why never use a number ≥ 5: Any integer x ≥ 5 can be replaced by 3 + (x-3), and since 3 × (x-3) > x for x ≥ 5 (because 3x - 9 > x implies 2x > 9, true for x ≥ 5), breaking it always helps.

Why prefer 3 over 2: We only need parts of size 2, 3, or 4. Since 4 = 2 + 2 and 2 × 2 = 4 (same product), we can treat 4 as two 2s. Comparing 3s and 2s: three 2s give 2³ = 8, while two 3s give 3² = 9. So 3s are more efficient.

The greedy strategy:

If n = 2: answer is 1 (must split into 1+1)
If n = 3: answer is 2 (must split into 1+2)
If n % 3 == 0: use all 3s → 3^(n/3)
If n % 3 == 1: the last remainder is 1, but 3+1=4 and 2×2=4 > 3×1=3, so replace one 3 with two 2s → 3^(n/3-1) × 4
If n % 3 == 2: use all 3s plus one 2 → 3^(n/3) × 2

Step-by-Step Explanation

Let's trace through with n = 10:

Step 1: Check n = 10. Since n > 3, we proceed with the greedy strategy.

Step 2: Compute n % 3 = 10 % 3 = 1. The remainder is 1.

Step 3: A remainder of 1 is problematic because multiplying by 1 wastes a factor. Instead, we take back one 3 from our pool and combine it with the 1 to make 4 (since 2 × 2 = 4 > 3 × 1 = 3).

Step 4: Count of 3s: n/3 = 3 (integer division), but we subtract 1 for the remainder adjustment → 2 threes.

Step 5: Remaining value: 10 - 2×3 = 4. We treat 4 as 2 × 2.

Step 6: Compute product: 3² × 4 = 9 × 4 = 36.

Step 7: Verify: 10 = 3 + 3 + 4, product = 3 × 3 × 4 = 36. Correct!

Let's also verify with n = 8 (remainder 2 case):

8 % 3 = 2
Count of 3s: 8/3 = 2 (integer division)
Remaining: 8 - 2×3 = 2
Product: 3² × 2 = 9 × 2 = 18
Verify: 8 = 3 + 3 + 2, product = 3 × 3 × 2 = 18. Correct!

Integer Break — Greedy Strategy for n = 10 — Watch how the greedy approach repeatedly extracts 3s from n, then adjusts the last piece based on the remainder to maximize the product.

Algorithm

Handle base cases: if n == 2, return 1; if n == 3, return 2
Initialize result = 1
While n > 4:
- Subtract 3 from n
- Multiply result by 3
Multiply result by the remaining n (which will be 2, 3, or 4)
Return result

Alternative O(1) formulation using modular arithmetic:

If n == 2, return 1; if n == 3, return 2
If n % 3 == 0: return 3^(n/3)
If n % 3 == 1: return 3^(n/3 - 1) × 4
If n % 3 == 2: return 3^(n/3) × 2

Code

class Solution {
public:
    int integerBreak(int n) {
        // Base cases: must make at least one cut
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int result = 1;
        // Keep extracting 3s while n > 4
        while (n > 4) {
            n -= 3;
            result *= 3;
        }
        // Multiply by the remaining piece (2, 3, or 4)
        return result * n;
    }
};

class Solution:
    def integerBreak(self, n: int) -> int:
        # Base cases: must make at least one cut
        if n == 2:
            return 1
        if n == 3:
            return 2
        
        result = 1
        # Keep extracting 3s while n > 4
        while n > 4:
            n -= 3
            result *= 3
        
        # Multiply by the remaining piece (2, 3, or 4)
        return result * n

class Solution {
    public int integerBreak(int n) {
        // Base cases: must make at least one cut
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int result = 1;
        // Keep extracting 3s while n > 4
        while (n > 4) {
            n -= 3;
            result *= 3;
        }
        // Multiply by the remaining piece (2, 3, or 4)
        return result * n;
    }
}

Complexity Analysis

Time Complexity: O(n)

The while loop runs n/3 times (subtracting 3 each iteration), so the time is O(n/3) which simplifies to O(n). With the mathematical O(1) formulation using modular arithmetic and exponentiation, this can be reduced to O(log n) using fast exponentiation, or even O(1) with direct computation since n ≤ 58.

Space Complexity: O(1)

We only use a constant number of variables (result, n). No arrays, hash maps, or recursive call stacks are needed.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Integer Break

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Greedy Mathematics

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis