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(logb(n)). In our case that isO(log_3n)O(log3n). 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
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?