O(log(n)) Time solution with explanation


  • 45
    K

    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);
            else 
                return 2 * (int) Math.pow(3, n/3);
        }
                
    }

  • 0
    L
    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
    K

    Thanks for pointing that out.


  • -3
    A

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

    class Solution {
    public:
        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
    Y

    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
    K

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


  • 0
    B
    This post is deleted!

  • 0
    G

    why was this given negative rating


  • 2
    A

    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.