💬 Discord
Sign In
NeetCode #893LC-342EasyMath & Geometry
← Back to All Problems

#893 · #342 · Power of Four(4 的幂)

📌 Problem Statement & Constraints

Given an integer n, return true if it is a power of four, otherwise false. Constraints: -2^31 <= n <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. A power of four must first be a power of two, which means it has exactly one set bit: n & (n - 1) == 0.
  2. Among powers of two, only those with an even exponent are powers of four, i.e. the single set bit must sit at an even index counted from the least significant bit.
  3. Masking with 0xAAAAAAAA (which has all odd bit positions set) must yield zero.
  4. A loop dividing by four also works but is O(log n) and needs an explicit non-positive check.

💻 Benchmark Python3 Implementation

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        # exactly one set bit AND that bit is at an even position
        return (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): two bit operations.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Accepting any power of two: 8 and 32 are powers of two but not powers of four, so the even-bit mask is essential.
  • Masking with 0x55555555 instead of 0xAAAAAAAA: that masks the even positions, which are exactly the valid ones, so the test would be inverted.
  • Ignoring non-positive input: n <= 0 must return false; 0 would otherwise satisfy the n & (n - 1) test.
  • Relying on a modulo loop: while n % 4 == 0 is correct but O(log n) and still needs the non-positive guard.