Power of Three

Solution

Vanilla Iteration

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

We could either increase or decrease w/ $O(\log n)$ 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 $2^{31} - 1$.

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

There exist a $maxPower=p^c q^c$, and a non-prime $n = p^a q^b$, where $a\neq b$. $n$ satisfies condition $maxPower \mod n = 0$ but is not a power of $pq$.

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 $2^{31} - 1$.

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