LeetCode 231: Power of Two Solution in Python – A Step-by-Step Guide

What Is LeetCode 231: Power of Two?

In LeetCode 231: Power of Two, you’re given an integer n, and your task is to return True if it’s a power of 2 (e.g., 1, 2, 4, 8, etc.) and False otherwise. Powers of 2 have a unique property—they’re numbers that can be expressed as 2 raised to some non-negative integer (2^k). This differs from tree-based challenges like LeetCode 230: Kth Smallest Element in a BST, focusing instead on number properties.

Problem Statement

• Input: An integer n.
• Output: A boolean—True if n is a power of 2, False otherwise.
• Rules: Handle positive, negative, and zero cases.

Constraints

• n: -2^31 to 2^31 - 1.

Examples

• Input: n = 1
• Output: True (1 = 2^0).
• Input: n = 16
• Output: True (16 = 2^4).
• Input: n = 3
• Output: False (not a power of 2).
• Input: n = 0
• Output: False (zero isn’t a power of 2).

Understanding the Problem: Identifying Powers of Two

To solve LeetCode 231: Power of Two in Python, we need to check if a number is of the form 2^k for some non-negative integer k. This isn’t about summarizing ranges like LeetCode 228: Summary Ranges—it’s about number properties. A key insight: powers of 2 have exactly one 1-bit in their binary representation (e.g., 4 = 100, 8 = 1000). We’ll explore two methods: 1. Best Solution (Bit Manipulation): O(1) time, O(1) space—fast and clever. 2. Alternative Solution (Division): O(log n) time, O(1) space—intuitive and simple.

Let’s start with the best solution.

Best Solution: Bit Manipulation Approach

Why This Is the Best Solution

The bit manipulation approach is our top pick for LeetCode 231 because it runs in constant time, uses a single operation to check the power-of-2 property, and leverages binary representation efficiently. It’s a brilliant trick that’s both fast and elegant, making it ideal for this problem.

How It Works

• A power of 2 has exactly one 1-bit in its binary form (e.g., 8 = 1000).
• Use the trick: n & (n-1) equals 0 for powers of 2 because subtracting 1 flips all bits after the rightmost 1 to 1 and the 1 to 0, leaving no overlap with the original number.
• Check n > 0 to exclude negative numbers and zero.

Step-by-Step Example

Example 1: n = 16

• Binary: 16 = 10000.
• n-1: 15 = 01111.
• n & (n-1): 10000 & 01111 = 00000 = 0.
• n > 0: True.
• Output: True.

Example 2: n = 10

• Binary: 10 = 1010.
• n-1: 9 = 1001.
• n & (n-1): 1010 & 1001 = 1000 ≠ 0.
• Output: False.

Example 3: n = 0

• n ≤ 0: False.
• Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # Line 1: Check if n is positive
        if n <= 0:
            return False  # Zero and negatives aren’t powers of 2

        # Line 2: Bit manipulation check
        return (n & (n - 1)) == 0  # True if only one 1-bit

• Line 1: Filters out non-positive numbers, as powers of 2 must be positive.
• Line 2: Uses bitwise AND to check if n has a single 1-bit (e.g., 4 & 3 = 100 & 011 = 0).
• Time Complexity: O(1) – constant time operation.
• Space Complexity: O(1) – no extra space.

Alternative Solution: Division Approach

Why an Alternative Approach?

The division approach checks if a number is a power of 2 by repeatedly dividing by 2 until it’s no longer divisible, then verifying if the result is 1. It’s a great alternative if you prefer a more intuitive, step-by-step method or aren’t comfortable with bit manipulation yet.

How It Works

• If n ≤ 0, return False.
• While n is even (n % 2 == 0), divide by 2.
• Check if the final result is 1 (a power of 2) or not.

Step-by-Step Example

Example 1: n = 8

• n = 8, 8 % 2 = 0, n = 4.
• n = 4, 4 % 2 = 0, n = 2.
• n = 2, 2 % 2 = 0, n = 1.
• n = 1, not even, stop.
• n == 1: True.
• Output: True.

Example 2: n = 6

• n = 6, 6 % 2 = 0, n = 3.
• n = 3, 3 % 2 = 1, stop.
• n ≠ 1: False.
• Output: False.

Example 3: n = -4

• n ≤ 0: False.
• Output: False.

Code for Division Approach

Copy codeclass Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # Line 1: Handle non-positive cases
        if n <= 0:
            return False

        # Line 2: Repeatedly divide by 2
        while n % 2 == 0:
            n = n // 2  # Integer division

        # Line 3: Check if result is 1
        return n == 1

• Line 1: Excludes zero and negatives.
• Line 2: Divides n by 2 while it’s even (e.g., 16 -> 8 -> 4 -> 2 -> 1).
• Line 3: Confirms if n reduces to 1, indicating a power of 2.
• Time Complexity: O(log n) – number of divisions is logarithmic.
• Space Complexity: O(1) – no extra space.

Comparing the Two Solutions

• Best Solution (Bit Manipulation):
• Pros: O(1) time, elegant, uses binary properties.
• Cons: Requires understanding bit operations.
• Alternative Solution (Division):
• Pros: Intuitive, easy to follow.
• Cons: O(log n) time, slower for large numbers.

The bit manipulation method is our best for its speed and efficiency.

Additional Examples and Edge Cases

Zero and Negatives

• Input: n = 0
• Output: False (n ≤ 0).
• Input: n = -2
• Output: False (n ≤ 0).
• Both handle correctly.

Large Power

• Input: n = 2^30 = 1073741824
• Bit: 100000... (30 zeros), 1073741824 & 1073741823 = 0.
• Division: Reduces to 1 after 30 steps.
• Output: True.

Non-Power

• Input: n = 12
• Bit: 1100 & 1011 = 1000 ≠ 0.
• Division: 12 -> 6 -> 3, stops at 3 ≠ 1.
• Output: False.

Complexity Breakdown

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

Bit manipulation wins on speed.

Key Takeaways for Beginners

• Power of 2: 2^k, one 1-bit in binary.
• Bit Manipulation: n & (n-1) checks single 1-bit.
• Division: Reduces to 1 if power of 2.
• Python Tip: Bitwise operators are fast—learn more at [Python Basics](/python/basics).

Final Thoughts: Master Powers of Two Like a Pro

LeetCode 231: Power of Two in Python is a delightful blend of math and coding ingenuity. The bit manipulation solution offers a lightning-fast trick, while the division approach keeps it simple and approachable. Want more number challenges? Try LeetCode 191: Number of 1 Bits or LeetCode 326: Power of Three. Ready to test your skills? Head to Solve LeetCode 231 on LeetCode and check those powers today!