Power of Four

Difficulty: Easy | Acceptance: 52.00% | Paid: No Topics: Math, Bit Manipulation, Recursion

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 == 4x.

• Examples
• Constraints
• Iterative Division
• Mathematical Logarithm
• Bit Manipulation - Power of 2 + Odd Position
• Bit Manipulation - Modulo 3
• Recursion

Examples

Input: n = 16
Output: true
Explanation: 24 = 16

Input: n = 5
Output: false

Input: n = 1
Output: true

Constraints

- -2^31 <= n <= 2^31 - 1

Iterative Division

Intuition Continuously divide n by 4 until it’s no longer divisible. If we reach 1, n was a power of 4.

Steps

• Handle edge case where n <= 0
• While n is divisible by 4, divide it by 4
• Check if the final result equals 1

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

Complexity

• Time: O(log₄n)
• Space: O(1)
• Notes: Simple and intuitive, but requires multiple iterations for large numbers

Mathematical Logarithm

Intuition If n is a power of 4, then log₄(n) must be an integer. We can check this using logarithms.

Steps

• Handle edge case where n <= 0
• Calculate log base 4 of n
• Check if the result is close to an integer (accounting for floating point precision)

import math

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        log_val = math.log(n, 4)
        return abs(log_val - round(log_val)) < 1e-10

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Constant time but relies on floating-point arithmetic which may have precision issues

Bit Manipulation - Power of 2 + Odd Position

Intuition A power of 4 is also a power of 2 (exactly one bit set), but the single bit must be at an even position (0, 2, 4, 6, …). The mask 0x55555555 has bits set at all even positions.

Steps

• Check n > 0
• Check if n is a power of 2 using n & (n-1) == 0
• Check if the single bit is at an even position using n & 0x55555555 != 0

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Most efficient bit manipulation approach with constant time operations

Bit Manipulation - Modulo 3

Intuition All powers of 4 are congruent to 1 modulo 3. Combined with the power of 2 check, this uniquely identifies powers of 4.

Steps

• Check n > 0
• Check if n is a power of 2 using n & (n-1) == 0
• Check if n % 3 == 1

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and n % 3 == 1

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Elegant mathematical property that avoids the need for a bitmask

Recursion

Intuition Recursively check if n/4 is a power of 4, with base cases for n <= 0, n == 1, and n not divisible by 4.

Steps

• Return false if n <= 0
• Return true if n == 1
• Return false if n is not divisible by 4
• Recursively call with n/4

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        if n % 4 != 0:
            return False
        return self.isPowerOfFour(n // 4)

Complexity

• Time: O(log₄n)
• Space: O(log₄n) for recursion stack
• Notes: Clean recursive solution but uses stack space proportional to the input size