Java 0ms with explanation


  • 1
    M

    Assume n = a + b, where a <= b, and an array, table[n+1], which is used to save the intermediate optimum results. Thus, we can always break n into only two positive integers. For example, when going to n = 5 = 2+3 = 2+2+1, we do not need to consider 2+2+1 as table[3] already saved the optimum result.

    After some runs, you will notice the magic number 3!

    n                  table[n]      optimization
    -------------------------------------------------
    2     1+1       1                
    3     1+2       2
    4     1+3       
           2+2       4                4 * 3^0
    5     1+4       
           2+3       6                2 * 3^1
    6     1+5       
           2+4       
           3+3       9                3 * 3^1
    7     1+6       
           2+5       
           3+4       12              4 * 3^1
    8     1+7       
           2+6
           3+5       18              2 * 3^2     
           4+4         
    9     1+8       
           2+7
           3+6       27              3 * 3^2
           4+5
    ...
    

    You will find when a=3, it always give the max value. I didn't find a proper way to explain it but you will notice when a>3, although the left part containing a will increase, the right part containing b will decrease to the same extent or even more. That is, for a=3, table[a+i]/table[a] <= table[b]/table[b-i], where i = 1,2,3...

    Then you can optimize it by finding the pattern shown above and here is the code.

    public class Solution {
        public int integerBreak(int n) {
            if(n<4) return n-1;
            int index = (n-2)/3;
            return (n-3*index) * (int)Math.pow(3, index);
        }
    }
    

    Any comments and suggestions are welcomed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.