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.
- -2³¹ <= n <= 2³¹ - 1
Intuition
Power of three leetcode problem 326 tests whether an integer is a power of three. Unlike powers of two and four, there is no bit pattern to exploit — three is not a power of two, so binary representation offers nothing.
The straightforward loop divides by 3 while the number is divisible, then checks whether 1 remains:
- Repeatedly divide by 3; the number is a power of three exactly when the process ends at 1 with no remainder along the way.
That is O(log n) and perfectly acceptable. Guarding n > 0 first matters, since zero and negatives are never powers of three and would otherwise loop forever or exit wrongly.
The follow-up asks for a solution without loops or recursion, and the trick uses the integer bound:
The largest power of three fitting in a signed 32-bit integer is 1162261467, which is 3¹⁹. Since 3 is prime, its only divisors that are powers of three are smaller powers of three — so n is a power of three exactly when it divides 1162261467 evenly and is positive.
That gives a one-line check: n > 0 && 1162261467 % n == 0.
This works only because 3 is prime. The same trick fails for composite bases like 4, where a non-power such as 2 also divides the largest power — worth understanding rather than memorising, since it explains why Power of Four needs a different approach entirely.
The logarithm method suffers the same floating-point unreliability as in Power of Four and should be avoided.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(log_3 n) time and O(1) space.
Note the absence of a bit trick
Three is not a power of two, so binary representation offers no pattern. The techniques from Power of Two and Power of Four do not transfer.
Divide repeatedly
While the number divides evenly by 3, divide it. It is a power of three exactly when the process ends at 1 with no remainder along the way.
Guard against zero and negatives
Check n > 0 first. Zero and negative values are never powers of three and would otherwise loop forever or exit incorrectly.
Use the integer bound for O(1)
The largest power of three in a signed 32-bit integer is 1162261467 = 3¹⁹. Test n > 0 && 1162261467 % n == 0.
Understand why that works
Only because 3 is prime — its only power-of-three divisors are smaller powers of three. The trick fails for composite bases like 4, where 2 also divides the largest power.
Cost of each approach
The loop is O(log n); the divisibility check is O(1). Both use O(1) space, and the logarithm method should be avoided for floating-point unreliability.
Solution & live demo
Common pitfalls
Omitting the positivity guard
while n % 3 == 0:
n //= 3
return n == 1if n <= 0:
return FalseZero 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
return math.log(n, 3).is_integer()
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
return (n & (n - 1)) == 0
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.
Edge cases
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.
Handled by an explicit early return of false, since the division loop assumes a positive starting value.
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.
Repeated integer division handles this exactly since it never leaves integer arithmetic, unlike a logarithm-based comparison which loses precision at scale.