342 - Power of Four

Difficulty: Easy | Pattern: Math / Bit Manipulation | Company tags: Amazon, Google

Problem Statement

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16
Output: true  (4^2 = 16)

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true  (4^0 = 1)

Follow-up: Could you solve it without loops or recursion?

Approach 1: Iterative Division — O(log n)

def isPowerOfFour(n: int) -> bool:
    if n <= 0:
        return False
    while n % 4 == 0:
        n //= 4
    return n == 1

Approach 2: Bit Tricks — O(1)

Powers of 4 satisfy two conditions:

1. Power of 2: n > 0 and (n & (n-1)) == 0 (only one bit set)
2. That bit is at an even position (0-indexed): The set bit must be at position 0, 2, 4, 6... — i.e., matching the mask 0x55555555 = 0b01010101010101010101010101010101

def isPowerOfFour(n: int) -> bool:
    return n > 0 and (n & (n-1)) == 0 and (n & 0x55555555) != 0

Approach 3: Math — O(1)

import math

def isPowerOfFour(n: int) -> bool:
    return n > 0 and math.log(n, 4) % 1 == 0

(Float precision issues possible — prefer bit approach for interviews.)

Dry Run

n = 16 (binary: 10000)

• n > 0 ✓
• n & (n-1) = 16 & 15 = 10000 & 01111 = 0 → power of 2 ✓
• 16 & 0x55555555: 0x55555555 = ...0101 0101; 16=10000; bit 4 (0-indexed): 0x55555555 has bit 4 = 1 ✓

n = 8 (binary: 1000):

• Power of 2 ✓ (8 & 7 = 0)
• 8 & 0x55555555: bit 3 in 0x55555555 = 0 → False ✓ (8 = 2^3, not 4^x)

Complexity

• Time: O(1) for bit approach
• Space: O(1)