Leetcode: 343. Integer Break

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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

Hint:

1. There is a simple O(n) solution to this problem.
2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

Solution (DP):
n = 0, => 0
n = 1, => 0
n = 2, 1 + 1 => 1
n = 3, 1 + 2 => 2
n = 4, 2 + 2 => 4
n = 5, 3 + 2 => 3 * 2 = 6
n = 6, 3 + 3 => 3 * 3 = 9
n = 7, 3 + 4 => 3 * 4 = 12
n = 8, 3 + 3 + 2 => 3 * 3 * 2 = 18
n = 9, 3 + 3 + 3 => 3 * 3 * 3 = 27
n = 10, 3 + 3 + 4 => 3 * 3 * 4 = 36
n = 11, 3 + 3 + 3 + 2 => 3 * 3 * 3 * 2 = 54
n = 12, 3 + 3 + 3 + 3 => 3 * 3 * 3 * 3 = 81

We can observe that for the result of A[i], it equals to results of A[i - 3] * 3. e.g.. n = 7, equals to n = 4 * 3. n = 8 equals to n = 5 * 3... So we can build up a DP array and store all the results before n. 

Code (Java):

public class Solution {
    public int integerBreak(int n) {
        if (n < 2) {
            return 0;
        }
        
        Integer[] table = new Integer[]{0, 0, 1, 2, 4, 6, 9};
        List<Integer> result = new ArrayList<>(Arrays.asList(table));
        
        for (int i = 7; i <= n; i++) {
            result.add(result.get(i - 3) * 3);
        }
        
        return result.get(n);
    }
}

Analysis: 
Time complexity is O(n), space complexity is O(n).

Solution 2: 
From the example shown above, we could see that the maximum product is generated by the maximum number of 3s. Therefore, we can try the maximum 3s. Note that if the number is less than 4, we just stop because 4 can be divided by 2 * 2 = 4, and for 3 2 and 1, no matter how we partition, the product must be less than the number itself. 

Code (Java):

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

Analysis:
Time complexity is O(n), space is O(1). 

Solution 3:
There is an O(1) time O(1) space solution. 

Code (Java):

public class Solution {
    public int integerBreak(int n) {
        if (n == 2 || n == 3) {
            return n - 1;
        }
        
        if (n == 4) {
            return 4;
        }
        
        if (n % 3 == 0) {
            int numOfThree = n / 3;
            return (int) Math.pow(3, numOfThree);
        } else if (n % 3 == 1) {
            int numOfThree = (n - 1) / 3 - 1;
            int result = (int) Math.pow(3, numOfThree) * 4;
            return result;
        } else {
            int numOfThree = (n - 2) / 3;
            return (int) Math.pow(3, numOfThree) * 2;
        }
        
    }
}