Valizada's blog

343. Integer Break, leetcode - Recursion, memoization

Another interesting leetcode problem that comes up often in Apple and Google interviews.

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

integer_break_examples

We can start from the smallest positive integer that can be broken into at least two possible integers and analyse it.

0 - Not positive 1 - Cannot be broken down 2 - 1 + 1. Only one possible way to break down. 3 - 2 + 1 = 1 + 1 + 1 = 1 + 2. 4 - 3 + 1 = 2 + 1 + 1 = 2 + 2 = 1 + 1 + 1 + 1 = 1 + 3

From above we can first spot our base case for the calculation. If n == 2, return 1;

Next, notice that for every next digit, we are reusing results from the previous one. We can now simply break down every digit into sums of two digits and then reuse previous results to build more complex combinations.

integer_break_digit_4

The trick is to compare maximum of the digit itself to the maximum of product of its break. For example, when we get to 2, its break is 1+1 and product 1*1. 2 itself is bigger than product. See the solution below.

class Solution {
    
    public int integerBreak(int n) {   
        if(n == 2) {
            return 1;
        }
        
        var max = Integer.MIN_VALUE;
        
        for(int i = 1; i < n; i++) {
            var firstBreak = Math.max(i, integerBreak(i));
            var secondBreak = Math.max(n - i, integerBreak(n-i));
            
            max = Math.max(max, firstBreak * secondBreak);
        }
        
        return max;
    }
}

As you could notice from the above drawing, we keep recalculating the same branches over and over. Hence, this leads to exponential computation and result will exceed time limits for large enough inputs. This is where memoization comes into play. Once the maximum has been calculated for an input, store it and then reuse.

class Solution {
    private final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int integerBreak(int n) {   
        // check if we know the result already
        if(map.containsKey(n)) {
           return map.get(n);
        }
        if(n == 2) {
            return 1;
        }
        
        var max = Integer.MIN_VALUE;
        
        for(int i = 1; i < n; i++) {
            var firstBreak = Math.max(i, integerBreak(i));
            var secondBreak = Math.max(n - i, integerBreak(n-i));
            
            max = Math.max(max, firstBreak * secondBreak);
        }
        
        // store maximum
        map.put(n, max);
        
        return max;
    }
}

Also note that, the simple optimization would be to loop till half of n as afterwards the branches are repeated with reverse order.

Visit this page for solution with bottom-up dynamic programming