JAVA solution very very ez!


  • 7
    Z
    public class Solution {
        public int integerBreak(int n) {
            if(n == 2) return 1;
            if(n == 3) return 2;
            if(n%3 == 0) return (int) Math.pow(3,n/3); 
            else if(n%3 == 1) return ((int)Math.pow(3,n/3))/3*4;
            else return ((int)Math.pow(3,n/3))*2;
        }
    }
    

    num 3 is the sum of 1,2 or 1,1,1 and both of the products is less than 3

    num 4 is the sum of 2,2 or 1,1,2 or ··· and all of them is no more than 4

    then 5 : 2 x 3 > 5 then 6 : 3 x 3 > 6

    this part seems like Greedy?

    so make more '3' as a break of n and here comes to the ac solution

    and it seems an O(lgN) solution?


  • 0
    S

    On the line with if(n%3 == 1), instead of doing ((int)Math.pow(3,n/3))/3, just do ((int)Math.pow(3,n/3-1))


  • 0
    L

    I searched several web, and seems the time complexity of Math.pow is nearly O(1). So it is O(1) solution.
    http://stackoverflow.com/questions/32418731/java-math-powa-b-time-complexity


  • 0
    Z

    @lfzh123 Thanks :D


Log in to reply
 

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