LeetCode #342 Easy

Power of Four

Determine whether an integer is a power of four using bit position, not just the power-of-two test.

mathbit-manipulationrecursion

02

Intuition

💡

The trap is reusing the power-of-two check and calling it done: 8 passes n & (n-1) == 0 because it has exactly one set bit, but 8 is 2^3, not a power of four. What power-of-two misses is WHERE that single bit sits. Powers of four (1, 4, 16, 64, ...) always have their lone set bit at an even position (0, 2, 4, ...), while powers of two that aren't powers of four (2, 8, 32, ...) have it at an odd position. So the fix is: keep the single-set-bit test as a first filter, then add a second check that the bit position is even -- either with a mask like 0x55555555 that only has bits set at even positions, or the arithmetic shortcut that (n-1) is divisible by 3 exactly when n is a power of four.

03

Approach

1

Filter to single-set-bit values

First confirm n > 0 and n & (n - 1) == 0, exactly as in Power of Two. This narrows candidates down to powers of two, but that set still includes non-powers-of-four like 2 and 8.

2

Check the bit sits at an even position

For a value that passed the single-bit test, check (n - 1) % 3 == 0. This works because powers of four minus one (0, 3, 15, 63, ...) are always multiples of 3, while powers of two at odd positions minus one (1, 7, 31, ...) are not.

3

Combine both conditions

Return True only when both the single-bit test and the even-position test pass. Either check alone is insufficient -- the single-bit test overaccepts values like 8, and the mod-3 test alone would need the single-bit guard to avoid false positives on numbers with multiple bits set.

04

Solution & live demo

python

▶1class Solution:
▶2    def isPowerOfFour(self, n: int) -> bool:
▶3        candidate = n
▶4        single_bit = candidate > 0 and (candidate & (candidate - 1)) == 0
▶5        if not single_bit:
▶6            return False
▶7        even_position = (candidate - 1) % 3 == 0
▶8        return even_position

05

Edge cases

n = 8 (2^3, odd position)

passes single-bit test but (8-1)%3=1 != 0, correctly returns False

n = 16 (4^2, even position)

passes both checks, returns True

n = 0 or negative

fails the n > 0 guard before any bit test runs

n = 1 (4^0)

single bit at position 0 (even), (1-1)%3=0, returns True

06

Complexity

Time

O(1)

Space

O(1)

constant number of bitwise and arithmetic operations