Power of Three LeetCode: The Max Power Trick Explained

LeetCode 326, Power of Three, asks a deceptively simple question: given an integer n, determine if it is a power of three. The values 1, 3, 9, 27, 81, 243 — you get the idea. Most people solve it with a loop in thirty seconds and move on. But this problem has a hidden gem.

The power of three leetcode problem is one of the rare cases where pure math gives you an O(1) solution that fits in a single line of code. The "max power trick" uses the fact that 3^19 = 1162261467 is the largest power of 3 that fits in a 32-bit signed integer. If that number is divisible by n (and n is positive), then n must be a power of 3.

This walkthrough covers both approaches — the straightforward loop and the elegant math solution — so you understand not just what the trick is, but why it works and when you can apply it to other problems.

The problem statement is minimal: given an integer n, return true if it is a power of three, and false otherwise. A number is a power of three if there exists an integer x such that n == 3^x. That means the valid values are 1 (3^0), 3 (3^1), 9 (3^2), 27 (3^3), 81, 243, 729, and so on up to 1162261467 (3^19).

The follow-up question is what makes this problem interesting: can you solve it without using any loop or recursion? That follow-up is a hint that a pure mathematical solution exists, and finding it is where the real learning happens.

Check power of three is straightforward to verify for any single value, but the challenge is doing it efficiently for arbitrary inputs within the 32-bit integer range.

The most intuitive approach is a simple loop. If n is positive, keep dividing by 3 as long as the result is divisible by 3. When you stop, check if the remaining value is 1. If it is, the original number was a power of three. If not, it was not.

The algorithm starts by handling the base case: if n is less than or equal to 0, return false immediately. No negative number or zero can be a power of three. Then enter a while loop: while n is divisible by 3 (n % 3 == 0), divide n by 3. After the loop, return whether n equals 1.

The time complexity is O(log base 3 of n) because you divide by 3 at each step. For a 32-bit integer, that is at most 19 iterations — practically instant. The space complexity is O(1). This is the leetcode 326 solution most people write first, and it passes all test cases comfortably.

Here is where the power of three math gets elegant. The largest power of 3 that fits in a 32-bit signed integer is 3^19 = 1162261467. Since 3 is a prime number, the only divisors of 1162261467 are powers of 3: 1, 3, 9, 27, 81, ..., 1162261467 itself.

That means if n is positive and 1162261467 is divisible by n (1162261467 % n == 0), then n must be a power of 3. Any non-power-of-3 divisor would require a prime factor other than 3, which 1162261467 does not have. The entire solution reduces to one line.

This is the power of three without loop approach the follow-up asks for. No recursion, no iteration, no bit manipulation. Just one modulo operation and one comparison. It runs in O(1) time and O(1) space, which is as efficient as a solution can possibly be.

The modulo power check works because of a fundamental property of prime numbers. When a number is a power of a prime p, its only prime factor is p itself. So 3^19 has the prime factorization 3 * 3 * 3 * ... * 3 (nineteen times). Every divisor of 3^19 must be some subset of those factors, which means every divisor is 3^k for some k between 0 and 19.

Consider why 6 does not divide 1162261467. The number 6 = 2 * 3, and since 1162261467 has no factor of 2, the division leaves a remainder. The same logic applies to 12, 15, 18, 21, or any number that contains a prime factor other than 3. The modulo check filters them all out in a single operation.

This is why the is power of three question has such an elegant answer. The mathematical structure of prime powers guarantees that the divisibility test is both necessary and sufficient. If n divides 3^19 and n is positive, then n is a power of 3. Period.

Edge cases for the power of three problem are straightforward but still worth verifying. The most common mistake is forgetting the n > 0 check, which causes zero and negative numbers to pass incorrectly.

n = 0: false. Zero is not a power of any positive integer. Without the n > 0 guard, 1162261467 % 0 would cause a division-by-zero error in most languages.

n = 1: true. This is 3^0 = 1. Both the loop approach and the max power approach handle this correctly — 1162261467 % 1 == 0, and dividing 1 by 3 leaves 1 with remainder 1 so the loop never executes and returns n == 1.

Negative numbers: false. No negative number is a power of three. The n > 0 check rejects all of them. Numbers like 6, 12, or 45 that contain 3 as a factor but are not pure powers of 3 are also correctly rejected because they have additional prime factors.

Power of Three is a masterclass in the gap between "correct" and "elegant." The loop solution is perfectly fine — it runs in under 20 iterations for any valid input. But the max power trick demonstrates a deeper understanding of number theory that interviewers notice and appreciate.

The broader lesson is that multiple approaches to the same problem exist at different levels of sophistication. The loop is O(log n) and intuitive. The math solution is O(1) and surprising. Knowing both shows range, and being able to explain why the math works shows depth.

This problem belongs to the same series as Power of Two (#231), which uses the n & (n-1) == 0 bit trick, and Power of Four (#342), which combines bit manipulation with a modulo check. Together they teach you three different mathematical tools: bit manipulation, prime factorization, and modular arithmetic.

Practice the power of three leetcode problem with YeetCode flashcards to lock in the max power trick. When you encounter a similar "is this a power of X" question in an interview, you will have the elegant solution ready before your interviewer finishes explaining the problem.