Power of Three: Loop vs. Math

LeetCode Power of Three (Problem 326) gives you an integer n and asks you to return true if it is a power of three, false otherwise. A number is a power of three when it equals 3^k for some integer k >= 0. That means 1, 3, 9, 27, 81, and 243 are all powers of three. Numbers like 2, 6, 10, and 45 are not.

The brute-force approach is a loop: keep dividing by 3 while the division is clean, then check what you are left with. There is also a math shortcut that skips the loop entirely using a single divisibility check. Both are worth knowing.

The approaches

Iterative division loop

The idea is simple. Start with n. As long as n is divisible by 3, divide it. When the loop ends, check whether you have reached 1. If you have, every factor you divided out was a 3, which means n was a power of three. If you have not, some other prime factor caused the loop to stop early.

One guard is required first: if n is less than 1, return False immediately. Zero and negative numbers can never be powers of three.

Math shortcut: largest power of three

The largest power of three that fits inside a 32-bit signed integer is 3^19 = 1162261467. Here is the key insight: if n is a power of three, then it must divide 3^19 exactly. That is because 3^k divides 3^19 for every k from 0 to 19.

The check becomes 1162261467 % n == 0. One modulo operation, no loop.

This trick relies on 3 being a prime number. Because 3 is prime, the only divisors of 3^19 are 1, 3, 9, 27, ... up to 3^19. If you tried this with a composite base like 4, the largest power of 4 that fits in 32 bits is 4^15 = 1073741824, but numbers like 2 and 8 also divide it cleanly even though they are not powers of four. The prime property guarantees that only true powers of three divide 3^19.

The solution

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

Walk through the logic:

1. Guard n < 1: If n is zero or negative, return False right away. There is no k for which 3^k is zero or negative.
2. Loop while n % 3 == 0: Each iteration divides n by 3. The loop continues as long as 3 divides evenly. If it does not, a non-three prime factor is present and the loop stops.
3. Return n == 1: After the loop, if n is 1, you divided out every factor and they were all 3s. If n is anything other than 1, a leftover factor remained, so n was not a pure power of three.

The math shortcut written out is:

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

Both return the same result for all valid inputs. The loop is easier to explain in an interview. The math version is O(1) with a single modulo.

Step-by-step walkthrough

Let's trace both approaches on two concrete inputs.

For n=45, the loop divides twice (45 to 15, 15 to 5) then stops because 5 is not divisible by 3. The leftover is 5, not 1, so the answer is False. For n=27, the loop divides cleanly all the way down to 1, confirming the answer is True.

Complexity analysis

The loop divides n by 3 each iteration, so it runs at most log base 3 of n times. That is approximately log(n) / log(3), which is O(log n). The math shortcut is a single modulo, making it constant time regardless of how large n is.

Building blocks

This problem is built from two reusable patterns.

1. Divide-until-remainder loop

Keep dividing a number by a factor while the remainder is zero, then check what is left. You see this same structure in problems that ask whether a number is composed entirely of certain prime factors, such as Ugly Number, where you strip out 2s, 3s, and 5s the same way.

while n % factor == 0:
    n //= factor

After the loop, n == 1 means all factors were consumed.

2. Largest-power-of-a-prime divisibility check

For any prime p, every power of p that is p^k with k >= 0 divides the largest power of p within a fixed range. This makes a single modulo check equivalent to the loop, but only when the base is prime. The check does not generalize to composite bases.

On CodeBricks, you drill each building block separately. When they appear combined in a new problem, you recognize both pieces without having to re-derive the logic from scratch.

Edge cases

n = 0: Zero is not a power of three. The guard n < 1 catches it immediately. The math shortcut also handles this because n > 0 fails. Return False.

n = 1: One is 3^0, a valid power of three. The loop condition 1 % 3 == 0 is false, so the loop never runs. The check n == 1 returns True.

n negative (e.g., n = -27): Negative numbers are never powers of three. The guard n < 1 returns False before the loop ever starts.

n = 2: Two is not divisible by 3, so the loop exits immediately with n = 2. Since 2 != 1, return False.

n = 3^19 = 1162261467: The largest power of three in a 32-bit signed integer. Both approaches return True. The loop divides 19 times. The math check computes 1162261467 % 1162261467 = 0.

n just above a power of three (e.g., n = 28): After dividing: 28 % 3 = 1, loop exits with n = 28. Return False.

From understanding to recall

You can follow this solution in a few minutes and nod along. But understanding is not the same as being able to write it cleanly under interview pressure two weeks from now.

The divide-until-remainder pattern is one that shows up repeatedly across problems like Ugly Number, Power of Two (with division), and others involving prime factorization. Drilling it with spaced repetition locks in the loop structure, the guard condition, and the final equality check so they flow out automatically.

The math shortcut is the kind of thing interviewers notice. Knowing it exists and being able to explain why it only works for prime bases is a signal that you have thought about the problem deeply, not just memorized a solution. CodeBricks helps you build that depth by connecting the pattern to the underlying number theory and making you retrieve it repeatedly at increasing intervals.

Related posts

• Power of Two - Same loop pattern with a bit trick shortcut. Comparing the two shows how the shortcut changes when the base is 2 versus 3.
• Happy Number - Same "keep dividing or reducing until you hit a known end state" pattern, combined with cycle detection to handle the case where the sequence never terminates.
• Add Digits - Another math problem where a loop (simulate digit summing) has a hidden O(1) closed-form solution once you see the modular arithmetic.