O(log(n)) Time solution with explanation

  • 45

    Given a number n lets say we have a possible product P = p1 * p2 * ... pk. Then we notice what would happen if we could break pi up into two more terms lets say one of the terms is 2 we would get the terms pi-2 and 2 so if 2(pi-2) > pi we would get a bigger product and this happens if pi > 4. since there is one other possible number less then 4 that is not 2 aka 3. Likewise for 3 if we instead breakup the one of the terms into pi-3 and 3 we would get a bigger product if 3*(pi-3) > pi which happens if pi > 4.5.

    Hence we see that all of the terms in the product must be 2's and 3's. So we now just need to write n = a3 + b2 such that P = (3^a) * (2^b) is maximized. Hence we should favor more 3's then 2's in the product then 2's if possible.

    So if n = a*3 then the answer will just be 3^a.

    if n = a3 + 2 then the answer will be 2(3^a).

    and if n = a3 + 22 then the answer will be 2 * 2 * 3^a

    The above three cover all cases that n can be written as and the Math.pow() function takes O(log n) time to preform hence that is the running time.

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

  • 0
    This post is deleted!

  • 1

    Nice job! Thanks.
    But the "a^3" in the following two lines should be "3^a":

    So if n = a*3 then the answer will just be a^3.
    if n = a3 + 2 then the answer will be 2a^3."

  • 0

    Thanks for pointing that out.

  • -3

    The same idea with you ,but use one line solution for the problem

    class Solution {
        int integerBreak(int n) {
            return n < 4 ? n - 1 : n%3 == 0 ? pow(3,n/3) : pow(3,n/3-1) * (2+2*(n%3));

  • 0

    I wrote the similar code, but why we don't need to consider overflow, i tried when n=70, our solution is -4, but the expected answer is 2066242608. How to deal with this problem?

  • 0

    Well you could always use long or Java BigInteger class to get a larger range.

  • 0
    This post is deleted!

  • 0

    why was this given negative rating

  • 2

    Great Job mate,
    But FYI Math.pow operation is iteration based hence it takes constant time not O(logn) ;) .

  • 1

    @adilliadil you mean O(n)?

Log in to reply

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