326 - Power of Three

Difficulty: Easy | Pattern: Math | Company tags: Google, Amazon

Problem Statement

Given an integer n, return true if it is a power of three, otherwise return false.

An integer n is a power of three if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27
Output: true   (27 = 3^3)

Example 2:

Input: n = 0
Output: false

Example 3:

Input: n = -1
Output: false

Constraints: -2^31 <= n <= 2^31 - 1

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

Keep dividing by 3 until no longer divisible. If we reach 1, it was a power of three.

The largest power of 3 that fits in a 32-bit integer is 3^19 = 1162261467. If n is a power of 3, it must divide this maximum value evenly.

def isPowerOfThree(n: int) -> bool:
    return n > 0 and 1162261467 % n == 0

This works because 3 is prime — so the only divisors of 3^19 are 3^0, 3^1, ..., 3^19.

Note: This trick only works because 3 is prime. It would NOT work for, say, powers of 12, since 12 is not prime.

import math

def isPowerOfThree(n: int) -> bool:
    if n <= 0:
        return False
    x = math.log(n, 3)
    return abs(x - round(x)) < 1e-10

Floating-point errors can cause this to fail for edge cases like n = 243 (3^5). Use with caution — the modulo approach is safer.

n = 27

Iteration	n	n % 3	n // 3
1	27	0	9
2	9	0	3
3	3	0	1
4	1	1 ≠ 0	stop

n = 1 → True ✓

n = 18 → 18 → 6 → 2 → 2%3=2≠0 → stop → n=2 ≠ 1 → False ✓