Repeatedly divide n by 3 while it is divisible by 3. If the final result is 1, then n is a power of three. Handle edge cases where n <= 0 by returning False immediately.
The largest power of 3 that fits in a 32-bit signed integer is $3^{19} = 1162261467$. If n is a power of three, then 1162261467 % n == 0. This avoids any loop or recursion.
""" 0326.1 - Solution 1 - Iterative Division """
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def isPowerOfThree(self, n: int) -> bool:
"""Power of Three Function"""
if n <= 0:
return False
while n % 3 == 0:
n //= 3
return n == 1
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().isPowerOfThree(27)) # True
print(Solution().isPowerOfThree(0)) # False
print(Solution().isPowerOfThree(-1)) # False
print(Solution().isPowerOfThree(9)) # True
print(Solution().isPowerOfThree(45)) # False
print(Solution().isPowerOfThree(1)) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0326.2 - Solution 2 - Math (No Loops / Recursion) """
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def isPowerOfThree(self, n: int) -> bool:
"""Power of Three Function"""
return n > 0 and 1162261467 % n == 0
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().isPowerOfThree(27)) # True
print(Solution().isPowerOfThree(0)) # False
print(Solution().isPowerOfThree(-1)) # False
print(Solution().isPowerOfThree(9)) # True
print(Solution().isPowerOfThree(45)) # False
print(Solution().isPowerOfThree(1)) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()