1. Introduction

LeetCode Problem 342 asks you to determine whether a given integer is a power of four. A number qualifies if it can be expressed as 4ⁿ for some non-negative integer n. Examples of valid results include 1, 4, 16, 64, 256, and so on. The task is to return true if the number meets this definition, otherwise return false.

---

2. What Defines a Power of Four

To understand how to detect powers of four, observe the numeric pattern:

4⁰ = 1
4¹ = 4
4² = 16
4³ = 64
4⁴ = 256

Two key insights emerge:

1. Every power of four is also a power of two.
2. Not every power of two is a power of four.

In binary, powers of four always have exactly one set bit, and that bit always appears at an even index position.

Examples:
1 → 0001 (bit index 0, even)
4 → 0100 (bit index 2, even)
16 → 10000 (bit index 4, even)

---

3. Core Insight Behind the Solution

A number is a power of four if and only if all three conditions below are true:

1. It is greater than zero.
2. It has exactly one set bit (power of two property).
3. The set bit is at an even position (power of four property).

The third condition is what separates powers of four from powers of two.

---

4. Algorithm Breakdown

1. Check if n is positive.
2. Use the expression n & (n – 1) to ensure only one bit is set.
3. Apply a bitmask, 0x55555555, to confirm that the set bit lies in an even position.
4. If all three checks succeed, return true.

The bitmask works because 0x55555555 has binary 1s only in even bit positions.

---

5. Java Implementation

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }

        if ((n & (n - 1)) != 0) {
            return false;
        }

        return (n & 0x55555555) != 0;
    }
}

---

6. Time and Space Complexity

Time Complexity
O(1) — All checks use constant-time bitwise operations.

Space Complexity
O(1) — No additional memory required.

---

7. Detailed Dry Run Examples

Example: n = 16

Step 1: 16 > 0 → valid
Step 2: 16 & 15 = 0 → only one bit set
Step 3: 16 & 0x55555555 = 16 → matches even position
Result: true

Example: n = 8

Step 1: 8 > 0 → valid
Step 2: 8 & 7 = 0 → has one bit set
Step 3: 8 & 0x55555555 = 0 → bit not in even position
Result: false

Example: n = 1

Step 1: 1 > 0
Step 2: 1 & 0 = 0
Step 3: 1 & 0x55555555 = 1
Result: true

Example: n = 0

Step 1 fails immediately
Result: false

---

8. Why Bitmasking Is Effective

The check n & (n – 1) ensures:

Only one bit is active.

The mask 0x55555555 ensures:

That bit is positioned in an even index.

This approach prevents accidental acceptance of values like 2, 8, or 32 and avoids floating-point precision issues or inefficient looping.

---

9. Common Mistakes (now using list items correctly)

• Assuming that every power of two is automatically a power of four, which causes values like 8 or 32 to be returned as true incorrectly.
• Using floating-point logarithms to compare exponents, which can introduce rounding errors and lead to unreliable results.
• Implementing repeated division by four in a loop, resulting in slower execution and unnecessary iteration when a constant-time solution exists.
• Failing to check that the number is positive, allowing zero or negative values to incorrectly qualify as valid outputs.
• Verifying only the single-bit property without validating the bit position, which allows incorrect results such as 2, 8, 32, or 128.