Python O(1) Solution 96.6%


  • 21
    D
    class Solution(object):
        def isPowerOfThree(self, n):
            return n > 0 and 1162261467 % n == 0

  • 1
    E

    hi,
    nice solution! Do you get 1162261467 programatically, or how do you get it?
    I'm guessing that's the greatest integer power of 3, Am I right?


  • 1
    D

    You are right, this is the maximum integer of pow 3 in python 2.7.
    I tested out the value knowing the maximum int is 2*31 - 1
    Next val 3
    1162261467 is a long int.


  • 0
    T

    I tried to get the value by using the following code, keep multiply by 3 until it overflows.

    int i = 1;
    while(i * 3 > i){
        i *= 3;
    }
    System.out.println(i);

  • 0
    D

    In python, this way doesn't work. overflow only happens when your full memory is full


  • 0
    E

    Also you could use the following math approach to get the max 32 bit integer power of 'x' number:
    pow( x,int( log(0x7FFFFFFF)/log(x) ) ).
    In this case x= 3, 0x7FFFFFFF isthe maximum 32 bit integer and the change of base with log(0x7FFFFFFF)/log(x) = logx(0x7FFFFFFF) which yields the number to which you have to power 'x' to get the biggest 32 bit integer.
    Note that int() returns the floor of a number passed as parameter.


  • 0
    L

    nice job! but it's not portable i think.


  • 2
    A

    Easy Python Solution

    class Solution(object):
        def isPowerOfThree(self, n):
            if n <= 0:
            	return False
    
            while n % 3 == 0:        	
            	n = n / 3
    
            return True if n == 1 else False

  • 0
    D

    Yes, it is an easy solution. But your complexity is O(logn). Besides, the return statement can be written as return n == 1. You don't have to make if test.


  • 0
    A

    You are correct on both observations.

    I am learning Python and found solving problems is the best way to do it.


  • 0
    D

    Yes, indeed, I learned a lot here as well.


  • 0
    B

    Why not use pow(x,int(log(0x7FFFFFFF,x)))


  • 0
    E

    It's exactly the same, just a different way to do it so that if you didn't had a built in like log(x, base) you would still be able to get it mathematically


  • 0
    B

    How do you know 3* 1162261467 is a long int? But on my system, it is a int.


  • 0
    E

    We're dealing with the assumption that we're working with 32-bit integers


  • 0
    B

    I find the max int in python is sys.maxint,which is 9223372036854775807


  • 0
    E

    That's not true when you're using languages like java, c, c++ and so many others. I'm not completely sure, but in my experience working with this OJ (leetcode), this web page uses int as the standard 32bit word


  • 0
    E

    It's not going to be portable and i haven't checked it , but i think you could use something like pow(x, (log(sys.maxint, x) )) if you feel more comfortable, it would be able to deal with the biggest int allowed in python, wich is bigger than the one yielded by a 32bit word


  • 0
    W

    @am78 no loop as the demand


  • 0
    A

    @am78
    The question mentioned that loop and recursion are not allowed.


Log in to reply
 

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