Problem Description

You are given a positive integer n (where n ≥ 2). You must break n into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

• You must use at least two positive integers (i.e., n cannot remain whole).
• The same number can be used multiple times in the sum.
• Order of summands doesn't matter (e.g., 2+3 is the same as 3+2).
• Return an integer representing the highest possible product.

Example: For n = 10, you can split it as 3 + 3 + 4, and the product is 3 × 3 × 4 = 36 (which is the maximum possible).

Thought Process

The problem asks us to split a number into at least two positive integers such that their sum is n and their product is as large as possible.

The brute-force way would be to try all possible ways to split n and compute the product for each, but this is inefficient for large n because the number of splits grows rapidly.

To optimize, we need to look for patterns. For example, splitting numbers into as many 3s as possible tends to give a bigger product. Why? Because for any integer n, the product of numbers that sum to n is maximized when those numbers are as close to e (Euler's number, about 2.718) as possible. Since we can only use integers, 2 and 3 are the best choices, and 3 is usually better.

So, we shift from brute-force enumeration to a mathematical or dynamic programming approach that exploits this insight.

Solution Approach

• Dynamic Programming (DP) Approach:
  • We create a DP array dp where dp[i] stores the maximum product for integer i.
  • For each i from 2 to n, we try every possible first split j (from 1 to i-1), and consider two cases:
    • Product of j and i - j (no further split).
    • Product of j and dp[i - j] (split i-j further).
  • We take the maximum of these products for all j and set it as dp[i].
  • Finally, dp[n] will be the answer.
• Mathematical/Greedy Approach:
  • For n > 4, the best strategy is to break n into as many 3s as possible. If the remainder is 1, we adjust by using a 4 instead (because 2×2 > 3×1).
  • This approach is optimal and runs in constant time.
• For most implementations, the DP approach is easier to understand, while the greedy approach is more efficient.

Example Walkthrough

Let's walk through the example of n = 10 using the DP approach:

1. We initialize dp[2] = 1 (since 1 + 1 = 2, product is 1).
2. For i = 3:
   • Try split at 1: 1 × 2 = 2, or 1 × dp[2] = 1 × 1 = 1 (max is 2).
   • Try split at 2: 2 × 1 = 2, or 2 × dp[1] = 2 × 0 = 0 (max is 2).
   • So, dp[3] = 2.
3. Continue filling dp up to dp[10]:
   • For i = 10, we check all splits:
     • 1 × 9, 1 × dp[9]
     • 2 × 8, 2 × dp[8]
     • 3 × 7, 3 × dp[7]
     • ... up to 9 × 1, 9 × dp[1]
   • We find that the best split is 3 + 3 + 4, giving 3 × 3 × 4 = 36.

The greedy approach would simply compute: 10 = 3 + 3 + 4, and multiply.

Time and Space Complexity

• Brute-force: Exponential time, because there are exponentially many ways to split n.
• Dynamic Programming: For each i (up to n), we try all splits j (up to i-1), so time complexity is O(n²). Space complexity is O(n) for the DP array.
• Greedy/Math Approach: Only a few arithmetic operations, so time complexity is O(1), and space is also O(1).

Thus, the greedy approach is optimal for large n.

Summary

The Integer Break problem challenges us to split a number into a sum of at least two positive integers to maximize their product. While brute-force is impractical, dynamic programming offers a clear, step-by-step solution, and mathematical insight reveals that breaking numbers into mostly 3s yields the highest product. The greedy approach is the most efficient and elegant, leveraging mathematical properties for a constant-time solution.

Code 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
        product *= n
        return product
      

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        product *= n;
        return product;
    }
};
      

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        product *= n;
        return product;
    }
}
      

var integerBreak = function(n) {
    if (n === 2) return 1;
    if (n === 3) return 2;
    let product = 1;
    while (n > 4) {
        product *= 3;
        n -= 3;
    }
    product *= n;
    return product;
};