Friedrich Ewald My Personal Website

Leetcode: Power of three

Given a number n, check if this number is a power of three, that is that it can be represented by 3^x. A straightforward solution looks as follows. Multiply by 3 until we reach n. If we’re greater than n, return False, and True otherwise. 

class Solution:
  def isPowerOfThree(self, n: int) -> bool:
    if n <= 0:
        return False
    
    x = 1
    while x < n:
        x *= 3
    return x == n
A mathematical more elegant solution looks as follows. Create the largest number that is less than 2^31: 3^19. Then use the modulo operator to test if the number is divisible without a rest. If this is the case, x*n == 3^19, therefore n is a valid number. 
class Solution:
  def isPowerOfThree(self, n: int) -> bool:
    return n > 0 and pow(3,19) % n == 0
Runtime: 80 ms, faster than 95.46% of Python3 online submissions for Power of Three. Memory Usage: 13.9 MB, less than 16.48% of Python3 online submissions for Power of Three.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts