Simple and easy Java solution with explanation


  • 2
    Z

    I get the idea from @Chuqi. Actually Chuqi explain very well.
    You could see Chuqi's idea here: [https://discuss.leetcode.com/topic/45341/an-simple-explanation-of-the-math-part-and-a-o-n-solution](link url)

    Now I give my complement:
    For an Integer we should consider whether should we break it down into two parts. If we break it and its product could be larger, absolutely we should!! So we find, when n = 2 ,3, after break, the product becomes smaller than the origin number. When n == 4 its maintain the same; When n > 4, no matter it is n/2 * n/2 or (n-1)/2 * (n + 1)/2, the product larger than n! So given an integer, if n > 4 we should break it, otherwise, not. So there are just 2,3,4 in the final answer. But if an integer could be broken into pure 3, or 4 or 2, or their mix, which one we should choose?

    Because 4 could be break down into 2 * 2 and the product is equal to 4. So we just consider the final result with only 3 and 2.

    Now we prove why we should have as much 3 as possible:
    For any Integer n, we could represent it as 3 * x + 2 * a, and if there is another way which 3 * y + 2 * b where x > y and b > a. So we have:

          3 * x + 2 * a = 3 * y + 2 * b = n with (x > y, b > a)
    

    now we have:
    (x - y) = 3/2(b - a)
    and the product of the left is : 3^x2^a
    the product of the right is: 3^y
    2^b

    So left/right = 3^(x-y)/2^(b-a) = 3^(3/2(b-a))/2^(b-a)

    Absolutely we could see left/right > 1!
    So if we want larger product we should have more 3!

    Code:

    public int integerBreak(int n) {
            if (n == 2) return 1;
            if (n == 3) return 2;
            if (n == 4) return 4;
            int mod = n % 3;
            int times = n / 3;
            if (mod == 1){
                times --;
                mod = 4;
            }
            else if (mod == 0) mod = 1;
            return (int)(Math.pow(3, times) * mod);
        }
    

Log in to reply
 

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