Domain 1EasyCORE

Power of Four

The problem asks us to determine whether a given integer `n` is a power of four. In other words, we need to check if there exists an integer `x` such that `n == 4^x`. The input is a single integer `n`, and the output should be a boolean value: `true` if `n` is a power of four, and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

342. Power of Four

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 0
Acceptance rate: 41.8%


Problem Breakdown

The problem asks us to determine whether a given integer n is a power of four. In other words, we need to check if there exists an integer x such that n == 4^x. The input is a single integer n, and the output should be a boolean value: true if n is a power of four, and false otherwise.

Inputs:

  • An integer n within the range -2^31 <= n <= 2^31 - 1.

Outputs:

  • A boolean value (true or false).

Implicit Constraints/Edge Cases:

  • Negative numbers cannot be powers of four.
  • The number 0 is not a power of four.
  • The number 1 is a power of four (since 4^0 = 1).
  • Powers of two that are not powers of four should return false.

Intuition

A brute-force approach would involve repeatedly dividing the number by 4 and checking if we eventually reach 1. However, this method has a time complexity of O(log₄(n)), which is acceptable but not optimal.

The key insight to improve upon this is recognizing that powers of four have specific properties in their binary representation:

  • Powers of four are also powers of two (since 4 = 2²).
  • In binary, powers of four have exactly one bit set and it must be at an even position (considering the least significant bit as position 0).

Using this insight, we can leverage bitwise operations to achieve a constant time solution.

Approach

  1. Check if n is positive: If n is less than or equal to zero, return false.
  2. Check if n is a power of two: A number is a power of two if it has exactly one bit set in its binary representation. This can be checked using the expression (n & (n - 1)) == 0.
  3. Check if the single set bit is at an even position: Powers of four have their single set bit at an even position. We can use a bitmask 0x55555555 (which has bits set at positions 0, 2, 4, …, 30) to check this condition.

If both conditions are satisfied, return true; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(1). The solution involves a constant number of bitwise operations.
  • Space Complexity: O(1). No additional space is used beyond a few variables.

Solution

def isPowerOfFour(n: int) -> bool:
    # Check if n is positive and a power of two
    if n <= 0 or (n & (n - 1)) != 0:
        return False
    
    # Check if the single set bit is at an even position
    return (n & 0x55555555) != 0

Edge Cases Handled

  • Negative numbers: The check (n <= 0) ensures that negative numbers are immediately returned as false.
  • Zero: Since zero is not a power of four, it will be correctly identified by the first condition.
  • One: The number 1 is a power of four (4^0 = 1), and the code will return true for this case.
  • Powers of two that are not powers of four: These numbers will pass the first check but fail the second, returning false.