Integer Break

NeetCode: Integer Break · LeetCode: 343. Integer Break · Difficulty: Medium

Given an integer n with 2 <= n <= 58, break it into the sum of k >= 2 positive integers and return the maximum product of those integers.

Example

Text

Input:  n = 2     Output: 1     (1 + 1)
Input:  n = 10    Output: 36    (3 + 3 + 4)

Brute force: plain recursion

Let best(n) be the best product when n must be split into at least two parts. Choose the first part i (from 1 to n - 1). The remainder n - i can either be left whole (product i * (n - i)) or be split further (product i * best(n - i)). So

best(n) = max over i of i * max(n - i, best(n - i)), with best(1) = 1 as the base case.

Each call spawns calls for every smaller value, so T(n) = T(1) + ... + T(n-1), which is O(2^n), because the same subproblems are solved repeatedly.

Java

class Solution {
    private int best(int n) {
        if (n <= 2) {
            return 1;
        }
        int result = 0;
        for (int i = 1; i < n; i++) {
            int rest = n - i;
            result = Math.max(result, i * Math.max(rest, best(rest)));
        }
        return result;
    }

    public int integerBreak(int n) {
        return best(n);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.integerBreak(2));
        System.out.println(solution.integerBreak(10));
        System.out.println(solution.integerBreak(3));
        System.out.println(solution.integerBreak(18));
    }
}

Output

Time: O(2^n). Space: O(n) recursion depth.

Better: bottom-up DP

Only n distinct subproblems exist, so store them. dp[i] is the best product for splitting i into at least two parts, computed for i = 2, 3, ... in order. Each cell costs O(i): dp[i] = max over j in 1..i of j * max(i - j, dp[i - j]).

Java

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int rest = i - j;
                dp[i] = Math.max(dp[i], j * Math.max(rest, dp[rest]));
            }
        }
        return dp[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.integerBreak(2));
        System.out.println(solution.integerBreak(10));
        System.out.println(solution.integerBreak(3));
        System.out.println(solution.integerBreak(18));
        System.out.println(solution.integerBreak(58));
    }
}

Output

Time: O(n^2). Space: O(n).

Optimal: use as many threes as possible

The table shows a pattern, which follows from a short argument. In an optimal split:

No part is >= 5: a part p >= 5 can be replaced by 3 and p - 3, and 3(p - 3) > p whenever p > 4.5.
No part is 1, since merging it into a neighbour increases the product. A part equal to 4 is the same as two 2s.
Three 2s (product 8) lose to two 3s (product 9), so at most two 2s appear.

So the answer is made of 3s plus at most two 2s. By n mod 3:

n = 2 gives 1 and n = 3 gives 2, because at least one split is required.
n % 3 == 0: 3^(n/3).
n % 3 == 1: 3^(n/3 - 1) * 4 (turn one 3 + 1 into 2 + 2).
n % 3 == 2: 3^(n/3) * 2.

Java

class Solution {
    // base^exp by repeated squaring, in long so that no intermediate step overflows.
    private long power(long base, int exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1; // n = 2 -> 1, n = 3 -> 2
        }
        int threes = n / 3;
        switch (n % 3) {
            case 0:
                return (int) power(3, threes);
            case 1:
                return (int) (power(3, threes - 1) * 4);
            default:
                return (int) (power(3, threes) * 2);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.integerBreak(2));
        System.out.println(solution.integerBreak(10));
        System.out.println(solution.integerBreak(3));
        System.out.println(solution.integerBreak(18));
        System.out.println(solution.integerBreak(58));
    }
}

Output

Math.pow returns a double, so the code uses its own power helper with long arithmetic. The helper squares the base each step (exponentiation by squaring). Time: O(log n). Space: O(1).

For n <= 58 the result fits in an int (n = 58 gives 1549681956). The product of the parts is the quantity that grows, so for n = 59 the answer would exceed Integer.MAX_VALUE, and the (int) cast would wrap to a wrong value.