# Power of Three

## # Solution

### # Vanilla Iteration

Could also do in recursion instead of while loop but omitted.

We could either increase or decrease w/ time and constant space.

#### # Increase

We could increase acc till it's equal to or larger than n.

def isPowerOfThree(self, n: int) -> bool:
if n<1: return False
elif n==1: return True
acc = 1
while acc<n:
acc *= 3
if acc==n:
return True
return False


#### # Decrease

We could decrease n till it's equal to or smaller than 1.

def isPowerOfThree(self, n: int) -> bool:
if n<1: return False
while n>1:
n /= 3
return n==1


## # Follow Up

Could you solve it without loops/recursion?

### # Modular Arithmatic

In __init__ method calculate self.maxPowerOfThree to be 1162261467, the largest power of 3 smaller than .

This solution of using maxPowerOfThree % n only works for prime n's. Here is the proof.

There exist a , and a non-prime , where . satisfies condition but is not a power of .

class Solution:
def __init__(self):
max_int = 2**31-1
self.maxPowerOfThree = 3
while self.maxPowerOfThree < max_int/3:
self.maxPowerOfThree *= 3

def isPowerOfThree(self, n: int) -> bool:
return n > 0 and self.maxPowerOfThree % n == 0


### # Integer Limitation

In __init__ method calculate all powers of 3 smaller than .

class Solution:
def __init__(self):
max_int = 2**31-1
self.powerOfThree = [1,3]
while self.powerOfThree[-1] < max_int/3:
self.powerOfThree.append(self.powerOfThree[-1]*3)

def isPowerOfThree(self, n: int) -> bool:
return n>0 and n in self.powerOfThree

Last Updated: 5/18/2020, 9:42:35 AM