Code Implementation

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # Check if n is positive, is a power of two, and only the 1-bit is in the correct position
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0
      

class Solution {
public:
    bool isPowerOfFour(int n) {
        // n must be positive, power of two, and the 1-bit must be in an odd position
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555);
    }
};
      

class Solution {
    public boolean isPowerOfFour(int n) {
        // n must be positive, power of two, and the 1-bit must be in an odd position
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }
}
      

var isPowerOfFour = function(n) {
    // n must be positive, power of two, and the 1-bit must be in an odd position
    return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
};
      

Problem Description

You are given an integer n. Your task is to determine whether n is a power of four. In other words, return true if there exists an integer x such that n == 4^x and x ≥ 0.

• The function must return true if n is a power of four, and false otherwise.
• Key constraints:
  • n can be any signed 32-bit integer.
  • There is only one valid answer for each input.
  • No elements or arrays are reused (the problem is about a single integer).

Thought Process

The problem asks if a given number is a power of four. At first glance, we might think about dividing n by 4 repeatedly and checking if we reach 1. This brute-force approach works, but it is not the most efficient.

If we think deeper, we realize that a power of four is also a power of two, but not all powers of two are powers of four. For example, 8 is 2³ (a power of two) but not a power of four. So, we need a way to distinguish powers of four from other powers of two.

The optimized approach leverages bitwise operations: powers of two have only one bit set, and powers of four have that bit in an odd position (counting from the least significant bit as position 1). This insight leads to a constant time solution.

Solution Approach

• Step 1: Check if n is positive.
  • All powers of four are positive. If n ≤ 0, return false.
• Step 2: Check if n is a power of two.
  • A power of two has only one bit set. We can check this with (n & (n - 1)) == 0.
  • If this is false, n is not a power of two, so it cannot be a power of four.
• Step 3: Check if the only set bit is in the correct (odd) position.
  • Powers of four have their single set bit in positions 1, 3, 5, ... (i.e., odd positions).
  • We use a hexadecimal mask: 0x55555555 in binary is 01010101...0101 (32 bits). This mask selects only the odd positions.
  • If n & 0x55555555 is not zero, it means the set bit is in the correct position for a power of four.
• Step 4: Return the result.
  • The final answer is n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0.

This approach is efficient and leverages bitwise operations for constant time checks.

Example Walkthrough

Let's take n = 16 as an example.

1. Is 16 positive? Yes.
2. Is 16 a power of two?
   • 16 in binary is 0001 0000.
   • 16 & (16 - 1) = 16 & 15 = 0001 0000 & 0000 1111 = 0
   • So, yes, it is a power of two.
3. Is the set bit in an odd position?
   • The mask 0x55555555 in binary is 0101 0101 0101 0101 0101 0101 0101 0101.
   • 16 & 0x55555555 = 0001 0000 & 0101 0101 ... = 0001 0000 (non-zero)
   • This means the set bit is in the correct position for a power of four.
4. Conclusion: 16 is a power of four (4²).

For another example, n = 8:

• 8 is positive and a power of two.
• However, 8 & 0x55555555 = 0, so the set bit is not in an odd position.
• Therefore, 8 is not a power of four.

Time and Space Complexity

• Brute-force approach:
  • Repeatedly divide n by 4 until you reach 1 or a non-integer.
  • Time Complexity: O(log₄n) ≈ O(log n)
  • Space Complexity: O(1) (no extra space used)
• Optimized bitwise approach (this solution):
  • All operations are bitwise and constant time.
  • Time Complexity: O(1)
  • Space Complexity: O(1)

The optimized approach is significantly faster, especially for large numbers.

Summary

To determine whether a number is a power of four, we check three things: it must be positive, it must be a power of two (only one bit set), and that bit must be in an odd position (using a special mask). This bitwise approach is elegant, fast, and requires no loops or recursion. The key insight is recognizing the unique pattern of bit positions for powers of four compared to other powers of two.