LeetCode #326 Easy

Power of Three

Check whether n is a power of three by repeatedly dividing by 3 instead of comparing logarithms, which floating point error can corrupt.

mathrecursion

Open on LeetCode ↗

02

Intuition

Using logarithms feels like the fast path: if log(n) / log(3) is a whole number, n is a power of three. But floating point arithmetic is not exact, and log(243) / log(3) can evaluate to something like 4.999999999999999 instead of a clean 5.0, which fails a naive integer check even though 243 really is 3^5. The reliable fix stays entirely in integer land: repeatedly divide n by 3 as long as it divides evenly, and see what is left over. If you strip out every factor of 3 and land exactly on 1, n was a pure power of three; if you hit a point where 3 no longer divides evenly and the remainder is not 1, n had some other prime factor mixed in. No floating point ever enters the picture.

How to spot this pattern

Unlike powers of two, there's no bit trick — 3 isn't the base the hardware counts in. Dividing out every factor of 3 and checking whether 1 remains is the honest O(log n) answer, and the positivity guard comes first as always.

03

Approach

1

Reject non-positive n immediately

Powers of three are always >= 1, so any n <= 0 can be answered false without doing any division.

2

Repeatedly divide by 3 while divisible

While n is evenly divisible by 3 (n % 3 == 0), divide it by 3 and continue. Each successful division strips exactly one factor of 3 out of n, using only integer arithmetic with no rounding error.

3

Check if the result is exactly 1

Once n is no longer divisible by 3, the loop stops. If what remains is exactly 1, every factor of n was a 3 and it is a genuine power of three; any other leftover value means n had a different prime factor.

04

Solution & live demo

▶1class Solution:
▶2    def isPowerOfThree(self, n: int) -> bool:
▶3        if n <= 0:
▶4            return False
▶5        while n % 3 == 0:
▶6            n //= 3
▶7        return n == 1

05

Common pitfalls

Omitting the positivity guard

✗ Wrong

while n % 3 == 0:
    n //= 3
return n == 1

✓ Right

if n <= 0:
    return False

Zero divides by 3 forever without changing, so the loop never terminates. Negative values fall straight through to a false n == 1 in some languages and loop in others.

Using a floating-point logarithm

✗ Wrong

return math.log(n, 3).is_integer()

✓ Right

while n % 3 == 0: n //= 3

log(243, 3) can evaluate to 4.999999999999999 due to rounding, reporting a genuine power of three as false. Integer division has no such failure mode.

Reaching for a bit trick

✗ Wrong

return (n & (n - 1)) == 0

✓ Right

while n % 3 == 0: n //= 3

That tests powers of two — the identity depends on binary representation and has no analogue for base 3. The only constant-time alternative is checking divisibility into the largest power of 3 that fits in an int.

06

Edge cases

n = 1 (3^0)

n % 3 != 0 immediately (1 is not divisible by 3), so the loop never runs, and n == 1 is true -- correctly a power of three.

n <= 0

Handled by an explicit early return of false, since the division loop assumes a positive starting value.

n has 3 as a factor but is not a pure power (e.g. 45 = 9 * 5)

Division strips the two factors of 3 to reach 5, then stops since 5 % 3 != 0, and 5 != 1, so the result is correctly false.

Large n near the int boundary (e.g. 3^19)

Repeated integer division handles this exactly since it never leaves integer arithmetic, unlike a logarithm-based comparison which loses precision at scale.

07

Complexity

Time

O(log_3 n)

Space

O(1)

undefined