Power of Three
franklinqin0 Math
# 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
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 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
1
2
3
4
5
2
3
4
5
# 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
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 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
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9