Two simple solutions without recursion or iteration: O(1) time and O(1) space


  • 10
    J

    Solution 1:

    class Solution(object):
        def isPowerOfThree(self, n):
            # 1162261467=3^19. 3^20 is bigger than int.
            return n > 0 and 1162261467 % n == 0
    

    Solution 2:

    class Solution(object):
        def isPowerOfThree(self, n):
            # power_list: 3^0, 3^1, ..., 3^19
            power_list = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467]
            return n in power_list

  • 0
    D

    I used solution 2.
    However the runtime only beat 79% of the submissions.
    What are the space to improve here?
    PS: Is it a bit dirty?


  • 0
    J

    I submitted solution 2 twice. The first time it beats 73%(404ms) while the second time it beats 99.37%(348ms)! So, I think it's a deviation of Python-compiler. PS: I prefer "tricky" rather than "dirty". :P


  • 0
    D

    Right, tricky is much better description


  • 0
    I

    solution 1 is cool and smart!


  • 0
    N

    Two things you can do to make it a bit faster:

    1.Define the powers outside of the method, therefor it will be created only once. It should be in the constructor of the class but I'm not sure if Leetcode is creating an instance for every test or not.
    2.You can use a set instead of a list to improve the search performance.

    powers = set([pow(3, i) for i in xrange(200)])
    class Solution(object):
        def isPowerOfThree(self, num):
            return num in powers
    

Log in to reply
 

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