# Problem

problem at: https://leetcode.com/problems/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