Simple Java solution with O(1) time and O(1) space


  • 0
    M

    Simple solution is to ensure you factor the given number into 2 and 3.

    The trick lies when you hit a number like 10: 3+3+3+1. You should try avoiding 1. This will result in removing a 3 and adding it to number of 2s required (You'll have to add two 2s to get it since 3+1 = 2+2 ).

    Java Solution:

    public int integerBreak(int n) {
            int three, two, temp;
            if(n ==2 || n == 3)
                return n-1;
            
            three = n/3;
            two = (n%3)/2;
            temp = n%3;
            
            if(temp == 1) {
                three--;
                two += 2;
                
            }
            return (int)Math.pow(3, three) * (int)Math.pow(2,two);
        }
    

Log in to reply
 

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