342. Power of Four - Explanation

1. Recursion

Intuition

A number is a power of four if we can repeatedly divide it by 4 until we reach 1. If at any point the number is not divisible by 4 (or becomes zero or negative), it cannot be a power of four.

This naturally leads to a recursive solution where we reduce the problem size by dividing by 4 at each step.

Algorithm

If n equals 1, return true (4^0 = 1).
If n is less than or equal to 0, or n is not divisible by 4, return false.
Recursively check if n / 4 is a power of four.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 4:
            return False
        return self.isPowerOfFour(n // 4)

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Iteration

Intuition

The same logic as recursion applies here, but we use a loop instead. We keep dividing n by 4 as long as it remains divisible. If we end up with 1, the original number was a power of four.

Algorithm

If n is negative, return false.
While n is greater than 1:
- If n is not divisible by 4, return false.
- Divide n by 4.
Return true if n equals 1, false otherwise.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        while n > 1:
            if n % 4:
                return False
            n //= 4

        return n == 1

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Math

Intuition

If n is a power of 4, then n = 4^k for some integer k. Taking the logarithm base 4 of both sides gives k = log4(n). If this result is an integer, then n is a power of four.

We check if the logarithm yields a whole number by verifying the remainder when divided by 1 is zero.

Algorithm

If n is less than or equal to 0, return false.
Compute log(n) / log(4) to get the base-4 logarithm.
Return true if this value has no fractional part (i.e., modulo 1 equals 0).

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and log(n, 4) % 1 == 0

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

4. Bit Manipulation

Intuition

Powers of four in binary are 1, 100, 10000, 1000000, etc. They have exactly one set bit, and that bit is always at an even position (0, 2, 4, ...).

We can check all even bit positions (0, 2, 4, ..., 30) and see if n equals exactly one of these values: 1, 4, 16, 64, and so on.

Algorithm

If n is negative, return false.
Iterate through even bit positions from 0 to 30 (step by 2):
- If n equals 1 << i (which is 4^(i/2)), return true.
If no match is found, return false.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        for i in range(0, 32, 2):
            if n == (1 << i):
                return True

        return False

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

5. Bit Mask - I

Intuition

A power of four must first be a power of two (exactly one bit set). We verify this using n & (n - 1) == 0. But not all powers of two are powers of four (e.g., 2 and 8 are not).

Powers of four have their single set bit at even positions. The mask 0x55555555 (binary: 01010101...) has 1s at all even positions. ANDing with this mask confirms the bit is at a valid position.

Algorithm

Check that n is positive.
Check that n is a power of two: (n & (n - 1)) == 0.
Check that the set bit is at an even position: (n & 0x55555555) == n.
Return true if all conditions are met.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) == n

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

6. Bit Mask - II

Intuition

Powers of four follow a pattern when divided by 3: 4^k mod 3 = 1 for all non-negative k. This is because 4 = 3 + 1, so 4^k = (3+1)^k, which when expanded always leaves remainder 1.

Powers of two that are not powers of four (like 2, 8, 32) give remainder 2 when divided by 3. This gives us a simple way to distinguish between them.

Algorithm

Check that n is positive.
Check that n is a power of two: (n & (n - 1)) == 0.
Check that n % 3 == 1 to confirm it's specifically a power of four.
Return true if all conditions are met.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n % 3 == 1)

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Confusing Power of Two with Power of Four

All powers of four are powers of two, but not vice versa. Checking only (n & (n - 1)) == 0 accepts values like 2, 8, and 32 which are powers of two but not four. You must add an additional check to verify the set bit is at an even position.

Floating-Point Precision Errors with Logarithms

Using log(n) / log(4) can introduce floating-point errors. For example, log(64) / log(4) might return 2.9999999... instead of exactly 3. Comparing with == 0 after modulo may incorrectly reject valid powers of four. Consider rounding or using integer-based approaches instead.