Integer Break — Leetcode Problem 343

Original Problem link: https://leetcode.com/problems/integer-break/

In this problem, we are given some integer n and we need to split it into the sum of 2 or more positive integers and find the max product of those integers.

Before we get into a more detailed explanation, here is my final solution:

class Solution {
    
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        
        // divide into 2, 3, 4...etc and distribute remainder evenly
        int maxProduct = 1;
        for (int i = 2; i <= n / 2; i++) {
            int parts = n / i;
            int remainder = n % i;
            int product = 1;
            for (int j = 0; j < i; j++) {
                if (j < remainder) {
                    product = product * (parts + 1);
                } else {
                    product = product * parts;
                }
            }
            maxProduct = Math.max(maxProduct, product);
        }
        return maxProduct;
    }
}

Before I came up with this solution, my first intuition was to essentially try every split and take the max product recursively:

  public int findIntegerBreak(int remaining, int product, int k) {
        if (remaining == 0) {
            if (k < 2) {
                // not a valid break
                return -1;
            }
            return product;
        }
        
        int maxProduct = 1;
        for (int i = 3; i <= remaining; i++) {
            maxProduct = Math.max(maxProduct, findIntegerBreak(remaining - i, product * i, k + 1));
        }
        return maxProduct;
  }

Obviously, this is not fast and did get time limit exceeded upon submission.

Thinking more, there’s no need to try every possible split. Looking at a few examples of correct splits:

5 = 2 + 3 => 2 * 3 = 6
10 = 3 + 3 + 4 => 3 * 3 * 4 = 36

We notice that in both of these splits, the numbers are close to the middle (n / 2). This leads to a potential solution idea, i.e. that we can divide into as equal of parts as possible, trying different-sized splits, with the remainder distributed evenly among the parts. We come up with the maximum product from among the different splits (2 through n / 2). Which is the crux of the implementation at the beginning of this post.

Viola! It works with 1 ms of runtime in the submission!