Leetcode problem: 343. Integer Break

Description:

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
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

• 2 <= n <= 58

Solution:

class Solution {
    public int integerBreak(int n) {

        int mid = n / 2;
        int secSum;

        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        int base;
        int sum;
        int max = 1;
        for (int i = 2; i <= mid; i++) {
            base = n;
            sum = 1;
            secSum = 1;
            while (base > 0) {
                if (base > i + 1) {
                    base = base - i;
                    sum = sum * i;
                } else {
                    sum = sum * base;
                    max = Math.max(max, sum);
                    break;
                }
            }
            max = Math.max(max, sum);
        }

        return max;
    }
}

Problem Statement

Given an integer n, break it into the sum of at least two positive integers, and maximize the product of those integers. Return the maximum product.

Approach Explanation

1. Handle small base cases directlyif (n == 2) return 1; if (n == 3) return 2;
   • If n = 2, only split is 1 + 1 → product = 1
   • If n = 3, best split is 2 + 1 → product = 2

2. Loop through possible split integers (i)int mid = n / 2; for (int i = 2; i <= mid; i++) { ... }
   • Any split integer cannot be more than n/2 (otherwise the remaining sum would be smaller than i)
   • Try each i as a potential factor in the product

3. Compute product for current factor ibase = n; sum = 1; while (base > 0) { if (base > i + 1) { base = base - i; sum = sum * i; } else { sum = sum * base; max = Math.max(max, sum); break; } }
   • base starts as n
   • Keep subtracting i from base and multiply into sum
   • If the remaining base ≤ i + 1, multiply it into sum and stop

4. Track the maximum productmax = Math.max(max, sum);
   • Update max after each factor iteration
   • At the end, max contains the maximum product possible

5. Return the result return max;

Example

Suppose n = 10:

• i = 2 → split as 2 + 2 + 2 + 2 + 2 → product = 32
• i = 3 → split as 3 + 3 + 4 → product = 36 ✅ (maximum)
• i = 4 → split as 4 + 3 + 3 → product = 36

So, answer = 36.

Time Complexity

• Outer loop: i = 2 to n/2 → O(n)
• Inner loop: repeatedly subtracting i from n → O(n)
• Total complexity: O(n²)

Space Complexity

• Only uses variables → O(1)

Key Idea

Works because it checks every possible integer factor for splitting.

The algorithm tries all possible splits using each integer i as a factor.

It multiplies numbers greedily and keeps track of the maximum product.