LeetCode 342: Power of Four Solution in Python – A Step-by-Step Guide

What Is LeetCode 342: Power of Four?

In LeetCode 342: Power of Four, you’re given an integer n, and your task is to determine if it’s a power of 4 (i.e., n = 4^k for some integer k ≥ 0). For example, 16 is (4²), but 20 isn’t. This problem tests your ability to recognize mathematical patterns efficiently, connecting to concepts in LeetCode 231: Power of Two and LeetCode 326: Power of Three.

Problem Statement

• Input: An integer n.
• Output: A boolean—True if n is a power of 4, False otherwise.
• Rules:
• n is a power of 4 if n = 4^k for some integer k ≥ 0.
• No loops or recursion allowed in the optimal solution (though we’ll explore both).

Constraints

• -2³¹ <= n <= 2³¹ - 1

Examples

• Input: 16
• Output: True (16 = 4²)
• Input: 5
• Output: False (Not a power of 4)
• Input: 1
• Output: True (1 = 4⁰)

Understanding the Problem: Spotting Powers of Four

To solve LeetCode 342: Power of Four in Python, we need to check if n can be expressed as 4^k. A naive approach—dividing by 4 repeatedly—works but takes O(log n) time. We can do better with bit manipulation! We’ll use:

• Best Solution (Bit Manipulation): O(1) time, O(1) space—pure brilliance.
• Alternative Solution (Iterative Division): O(log n) time, O(1) space—simple and clear.

Let’s start with the bit manipulation solution, explained in a beginner-friendly way.

Best Solution: Bit Manipulation Trick

Why This Is the Best Solution

The bit manipulation trick is the top choice for LeetCode 342 because it’s constant-time—O(1) time, O(1) space—and avoids loops or recursion entirely. It uses two key properties: powers of 4 are powers of 2 (with only one 1-bit), and their 1-bit appears at even positions in the binary representation. It’s like a secret code detector—fast and elegant!

How It Works

Think of this as a bit detective:

• Step 1: Check Power of 2:
• Powers of 4 are powers of 2: n & (n-1) == 0 (only one 1-bit).
• Step 2: Check Even Position:
• Powers of 4 have 1-bit at positions 0, 2, 4, ... (even indices).
• Use mask 0x55555555 (0101... in binary) to check: n & 0x55555555 == n.
• Step 3: Validate Positive:
• n > 0 (powers of 4 are positive).
• Step 4: Why It Works:
• Combines power-of-2 check with position constraint.
• Single operation covers all cases.

It’s like a one-line bit magic spell!

Step-by-Step Example

Example: n = 16

• Binary: 16 = 10000
• Power of 2: 16 & 15 = 10000 & 01111 = 0, True
• Even Position: 16 & 0x55555555 = 10000 & 010101... = 10000 = 16, True
• Positive: 16 > 0, True
• Result: True (16 = 4²)

Example: n = 5

• Binary: 5 = 101
• Power of 2: 5 & 4 = 101 & 100 = 100 ≠ 0, False
• Result: False (not even a power of 2)

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # Check positive, power of 2, and even 1-bit position
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) == n

• Line 3: Single line check:
• n > 0: Ensures positive.
• n & (n-1) == 0: Confirms power of 2 (one 1-bit).
• n & 0x55555555 == n: Ensures 1-bit at even position.
• Time Complexity: O(1)—constant-time bit operations.
• Space Complexity: O(1)—no extra space.

This is like a bit-powered lightning bolt—instant and sleek!

Alternative Solution: Iterative Division

Why an Alternative Approach?

The iterative division approach—O(log n) time, O(1) space—divides n by 4 repeatedly until it’s 1 or not divisible, offering a hands-on way to see if it’s a power of 4. It’s simpler to understand but slower, making it a great learning tool. It’s like peeling layers to check the core—straightforward and tangible!

How It Works

Divide and check:

• Step 1: Handle edge cases (n ≤ 0).
• Step 2: While n > 1:
• If n % 4 ≠ 0, return False.
• Divide n by 4.
• Step 3: Check if n = 1 (a power of 4).

Step-by-Step Example

Example: n = 16

• Divide: 16 / 4 = 4
• Divide: 4 / 4 = 1
• Result: True (16 = 4²)

Example: n = 20

• Divide: 20 % 4 = 0, 20 / 4 = 5
• Divide: 5 % 4 ≠ 0
• Result: False

Code for Iterative Approach

Copy codeclass Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False

        while n > 1:
            if n % 4 != 0:
                return False
            n //= 4

        return n == 1

• Time Complexity: O(log n)—number of divisions.
• Space Complexity: O(1)—just n.

It’s a step-by-step power checker—clear and steady!

Comparing the Two Solutions

• Bit Manipulation (Best):
• Pros: O(1) time, O(1) space, no loops.
• Cons: Requires bit insight.
• Iterative Division (Alternative):
• Pros: O(log n) time, O(1) space, easy to follow.
• Cons: Slower for large n.

Bit manipulation wins for speed.

Additional Examples and Edge Cases

• 4: True (4¹).
• -4: False (negative).
• 0: False (not a power).

Both handle these, but bit manipulation is faster.

Complexity Breakdown

• Bit Manipulation: Time O(1), Space O(1).
• Iterative Division: Time O(log n), Space O(1).

Bit manipulation is the clear champ.

Key Takeaways

• Bit Manipulation: Bit magic—fast!
• Iterative Division: Divide and check—simple!
• Python: Bit ops shine—see [Python Basics](/python/basics).
• Powers: Patterns unlock answers.

Final Thoughts: Spot the Power

LeetCode 342: Power of Four in Python is a math-meets-coding delight. The bit manipulation solution offers instant elegance, while iterative division provides a tangible process. Want more power challenges? Try LeetCode 231: Power of Two or LeetCode 326: Power of Three. Ready to check? Head to Solve LeetCode 342 on LeetCode and power up your skills today!