Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up: Could you do it without using any loop / recursion?

最直接的方法就是不停地除以3,看最后的余数是否为1,要注意考虑输入是负数和0的情况

Time complexity :O(log_b(n))O(log​b​​(n)). In our case that isO(log_3n)O(log​3​​n). The number of divisions is given by that logarithm.

  • Space complexity :O(1)O(1). We are not using any additional memory.

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        while n%3 == 0 and n:
            n = n/3
        if n == 1:
            return True
        return False

https://discuss.leetcode.com/topic/33536/a-summary-of-all-solutions-new-method-included-at-15-30pm-jan-8th/2

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and (math.log10(n)/math.log10(3))%1==0

最后一直方法是recursion:

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n == 1:
            return True
        if n == 0 or n % 3 > 0:
            return False
        return self.isPowerOfThree(n / 3)

Last updated

Was this helpful?