Power of Four

LeetCode Power of Four (Problem 342) gives you an integer n and asks you to return true if n is a power of four, false otherwise. A number is a power of four if it equals 4^k for some integer k >= 0. That means 1, 4, 16, 64, and 256 all qualify. The problem asks: could you solve it without loops or recursion?

The answer is yes, using a clever combination of bit tricks and either a bitmask or modular arithmetic.

The key insight

Powers of four share two special properties when you look at them in binary.

First, every power of four is also a power of two, so it has exactly one bit set. That means the n & (n-1) == 0 trick applies here too.

Second, powers of four have their single set bit at an even position, specifically positions 0, 2, 4, 6... counting from the right. Why? Because 4^k = (2^2)^k = 2^(2k), and 2k is always even. So the set bit lands at position 0 when k=0, position 2 when k=1, position 4 when k=2, and so on.

Powers of two that are NOT powers of four, such as 2, 8, and 32, have their set bit at odd positions (1, 3, 5...).

The three-condition approach (bitmask)

You need three conditions to all be true:

Condition 1: n is positive. Zero and negative numbers can never be powers of four.

Condition 2: n is a power of two. Check this with n & (n-1) == 0. This confirms there is exactly one set bit.

Condition 3: the set bit is at an even position. The mask 0xAAAAAAAA is a 32-bit number with 1s at all odd positions (positions 1, 3, 5, 7...). It looks like 10101010...10101010 in binary. If you AND n with this mask and get zero, then n has no bits in any odd position. Since you already know n has exactly one bit, that bit must be at an even position, confirming it is a power of four.

def isPowerOfFour(n):
    return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

The modulo approach (number theory)

There is an alternative third condition using modular arithmetic. Notice that 4 mod 3 = 1. That means 4^k mod 3 = 1^k = 1 for any k. So every power of four leaves a remainder of 1 when divided by 3.

Now what about powers of two that are not powers of four? Those look like 4^k * 2. Modulo 3, that gives 1 * 2 = 2. So they always leave remainder 2.

This gives you a clean alternative:

def isPowerOfFour(n):
    return n > 0 and (n & (n - 1)) == 0 and n % 3 == 1

Both versions run in O(1) time and use O(1) space. The bitmask version is pure bit manipulation. The modulo version draws on a bit of number theory. Both are worth knowing.

Step-by-step walkthrough

Walking through n = 16:

• 16 is greater than 0: pass.
• 16 & 15 = 10000 & 01111 = 00000 = 0: pass, it is a power of two.
• 16 & 0xAAAAAAAA = 0: the set bit is at position 4, which is even: pass.
• 16 % 3 = 1: confirms with the modulo approach as well.

Walking through n = 8:

• 8 is greater than 0: pass.
• 8 & 7 = 1000 & 0111 = 0000 = 0: pass, it is a power of two.
• 8 & 0xAAAAAAAA = 8 (non-zero): the set bit is at position 3, which is odd: fail.
• 8 % 3 = 2: the modulo approach also rejects it.

Eight is a power of 2 but not a power of 4.

Complexity analysis

Both are constant time. There are no loops, no recursion, no data structures. Just arithmetic on a fixed 32-bit integer.

Building blocks

Bit isolation: n & (n-1)

This trick strips away the lowest set bit from n. When n has exactly one set bit, the result is zero. You see the same pattern in Number of 1 Bits (LeetCode 191) and Power of Two (LeetCode 231). Recognizing it instantly saves you the mental overhead of re-deriving it under pressure.

Bitmask position filtering

The mask 0xAAAAAAAA encodes a constraint about which bit positions are allowed. This technique generalizes: you can build masks that represent any pattern of allowed positions and use AND to check membership. It is a compact, branchless way to enforce positional constraints.

Modular arithmetic with powers

When you need to distinguish 4^k from 2^(2k+1), the observation that 4 mod 3 = 1 and 2 mod 3 = 2 gives you a number-theory fingerprint. The same reasoning appears whenever you need to separate a subset of powers from a larger family using divisibility properties.

Edge cases

n = 1: One equals 4^0, so it is a valid power of four. 1 & 0 = 0 (power of two check passes). The set bit is at position 0 (even, mask check passes). 1 % 3 = 1 (modulo check passes). Returns true.

n = 0: Zero is not a power of four. The first condition n > 0 catches it immediately and returns false.

Negative numbers: No negative number can be a power of four. The n > 0 guard rejects them.

n = 8: Eight is 2^3, a power of two but not a power of four. It passes the power-of-two check but fails both the bitmask and modulo checks. Returns false.

n = 2: Two is 2^1. It passes the power-of-two check, but 2 & 0xAAAAAAAA != 0 because position 1 is odd. Also 2 % 3 = 2. Returns false.

n = 64: Sixty-four is 4^3. Binary 01000000, set bit at position 6 (even). 64 & 0xAAAAAAAA = 0. 64 % 3 = 1. Returns true.

From understanding to recall

Reading this and nodding is not the same as being able to write it cleanly two weeks from now. The three-condition check has three distinct moving parts: the positivity guard, the power-of-two test, and either the bitmask or the modulo. Under interview pressure it is easy to nail two out of three and blank on the third.

Spaced repetition drills each piece separately. You practice writing n & (n - 1) == 0 until it is automatic. You practice constructing the mask argument until you can explain why 0xAAAAAAAA covers odd positions. You practice the modular arithmetic argument until the 4 mod 3 = 1 insight feels natural rather than mysterious.

CodeBricks connects these building blocks across related problems. When Power of Two, Number of 1 Bits, and Power of Four all feed into the same review queue, you start to see how the same two or three primitives recombine in different ways. That cross-problem fluency is what separates people who derive solutions slowly from people who recognize them instantly.

Related posts

• Power of Two - The n & (n-1) == 0 trick lives here. Power of Four adds the position constraint on top of it.
• Power of Three - The modulo shortcut for powers of three uses similar number theory reasoning. Comparing the two reveals why primality matters for the largest-power trick but not for the modulo-3 trick used here.
• Number of 1 Bits - Deep dive into n & (n-1) as a loop that counts set bits. Understanding it in that context makes the single-bit check feel obvious.