LeetCode 693: Binary Number with Alternating Bits Solution in Python – A Step-by-Step Guide

What Is LeetCode 693: Binary Number with Alternating Bits?

In LeetCode 693: Binary Number with Alternating Bits, you’re given a positive integer n, and your task is to determine if its binary representation has alternating bits—meaning no two adjacent bits are the same (e.g., 0-1-0-1). Return True if the bits alternate, False otherwise. For example, with n = 5 (binary 101), the bits alternate (1-0-1), so return True. With n = 7 (binary 111), they don’t (1-1-1), so return False. The problem tests your ability to analyze a number’s binary form efficiently.

Problem Statement

• Input:
• n: Positive integer.
• Output: A boolean—True if binary bits alternate, False otherwise.
• Rules:
• Check binary representation of n.
• Bits must alternate (e.g., 0-1 or 1-0).
• No two adjacent bits can be the same.
• Leading zeros don’t count (e.g., 5 is 101, not 0101).

Constraints

• 1 ≤ n ≤ 10⁹.

Examples

• Input: n = 5
• Output: True (Binary: 101, alternates)
• Input: n = 7
• Output: False (Binary: 111, doesn’t alternate)
• Input: n = 10
• Output: True (Binary: 1010, alternates)
• Input: n = 11
• Output: False (Binary: 1011, doesn’t alternate)

These examples set the bits—let’s solve it!

Understanding the Problem: Checking Alternating Bits

To solve LeetCode 693: Binary Number with Alternating Bits in Python, we need to determine if the binary representation of n has alternating bits—no two adjacent bits are the same. A brute-force approach—converting to binary string and checking each pair—would be O(log n) for conversion and iteration, reasonable for n ≤ 10⁹ but not the fastest. Since we’re working with bits, bit manipulation or string iteration can solve this efficiently. We’ll use:

• Best Solution (Bit Manipulation with Shift): O(log n) time, O(1) space—fast and direct.
• Alternative Solution (String Conversion with Iteration): O(log n) time, O(log n) space—simple but less efficient.

Let’s start with the bit manipulation solution, breaking it down for beginners.

Best Solution: Bit Manipulation with Shift

Why This Is the Best Solution

The bit manipulation with shift approach is the top choice for LeetCode 693 because it’s highly efficient—O(log n) time with O(1) space—and directly inspects n’s bits using bitwise operations, avoiding string conversion and extra memory. It fits constraints (n ≤ 10⁹) perfectly and is intuitive once you see the shift logic. It’s like flipping through the bits with a magnifying glass, checking each pair without writing anything down!

How It Works

Think of this as a bit flipper:

• Step 1: Compare Adjacent Bits:
• Use n & 1 to get the least significant bit (LSB).
• Shift n right (n >> 1) to check next bit.
• Step 2: Check Alternation:
• If current bit equals previous bit (both 0 or 1), return False.
• Update previous bit, continue until n = 0.
• Step 3: Handle Edge Cases:
• Single bit (e.g., n=1) is True (no adjacent bits).
• Step 4: Return Result:
• Return True if all bits alternate.

It’s like a bit checker—shift and compare!

Step-by-Step Example

Example: n = 5 (binary 101)

• Step 1: Init:
• n = 5 (101), prev = None.
• Step 2: Check:
• n = 5 (101): LSB = 1 (5 & 1), prev = 1, n = 2 (10).
• n = 2 (10): LSB = 0 (2 & 1), 0 ≠ 1, prev = 0, n = 1 (1).
• n = 1 (1): LSB = 1 (1 & 1), 1 ≠ 0, prev = 1, n = 0 (0).
• n = 0: Done.
• Step 3: All alternated (1-0-1).
• Step 4: Return True.
• Output: True.

Example: n = 7 (binary 111)

• Step 1: n = 7 (111), prev = None.
• Step 2: Check:
• n = 7 (111): LSB = 1, prev = 1, n = 3 (11).
• n = 3 (11): LSB = 1, 1 = 1, return False.
• Step 4: Return False.
• Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        # Step 1: Get first bit and initialize prev
        prev = n & 1  # Least significant bit
        n >>= 1       # Shift right

        # Step 2: Check remaining bits
        while n > 0:
            curr = n & 1
            if curr == prev:  # Adjacent bits same
                return False
            prev = curr
            n >>= 1

        # Step 3: All bits alternated
        return True

• Line 4: Get LSB: n & 1 extracts rightmost bit.
• Line 5: Shift: n >>= 1 moves to next bit.
• Lines 8-13: Check:
• Extract current bit, compare with prev, update prev, shift.
• Line 16: Return True if all alternated.
• Time Complexity: O(log n)—number of bits in n.
• Space Complexity: O(1)—two variables.

This is like a bit inspector—shift and flip!

Alternative Solution: String Conversion with Iteration

Why an Alternative Approach?

The string conversion with iteration approach converts n to binary—O(log n) time, O(log n) space. It’s simpler for beginners, turning the number into a string and checking pairs, but uses more space and steps. It’s like writing out the bits on paper and checking them one-by-one!

How It Works

Picture this as a bit writer:

• Step 1: Convert to binary string:
• Use bin(n)[2:] to get binary without "0b".
• Step 2: Check adjacent bits:
• Iterate string, compare each pair.
• Step 3: Return result:
• True if all alternate, False if any match.

It’s like a string scanner—write and check!

Step-by-Step Example

Example: n = 5

• Step 1: Binary = "101".
• Step 2: Check:
• 1-0: Different.
• 0-1: Different.
• Step 3: Return True.
• Output: True.

Example: n = 7

• Step 1: Binary = "111".
• Step 2: Check:
• 1-1: Same, return False.
• Step 3: Return False.
• Output: False.

Code for String Approach

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        # Step 1: Convert to binary string
        binary = bin(n)[2:]  # Remove "0b" prefix

        # Step 2: Check adjacent bits
        for i in range(1, len(binary)):
            if binary[i] == binary[i - 1]:
                return False

        # Step 3: All bits alternated
        return True

• Line 4: Convert: bin(n)[2:] to binary string.
• Lines 7-9: Check:
• Compare each pair, return False if same.
• Line 12: Return True if all alternated.
• Time Complexity: O(log n)—string length and iteration.
• Space Complexity: O(log n)—binary string.

It’s a string checker—convert and scan!

Comparing the Two Solutions

• Bit Manipulation (Best):
• Pros: O(log n) time, O(1) space, fast and direct.
• Cons: Bitwise ops less intuitive.
• String Conversion (Alternative):
• Pros: O(log n) time, O(log n) space, simple to understand.
• Cons: More space, extra conversion step.

Bit manipulation wins for efficiency.

Additional Examples and Edge Cases

• Input: n = 1
• Output: True (Binary: 1, no adjacent bits).
• Input: n = 2
• Output: True (Binary: 10, alternates).
• Input: n = 3
• Output: False (Binary: 11, doesn’t alternate).

Bit manipulation handles these well.

Complexity Breakdown

• Bit Manipulation: Time O(log n), Space O(1).
• String Conversion: Time O(log n), Space O(log n).

Bit manipulation is optimal.

Key Takeaways

• Bit Manipulation: Shift checking—smart!
• String Conversion: String scanning—clear!
• Bits: Flipping is fun.
• Python Tip: Bits rock—see Python Basics.

Final Thoughts: Crack That Binary Case

LeetCode 693: Binary Number with Alternating Bits in Python is a fun bit challenge. Bit manipulation with shift offers speed and elegance, while string conversion provides a clear baseline. Want more? Try LeetCode 191: Number of 1 Bits or LeetCode 338: Counting Bits. Ready to flip? Head to Solve LeetCode 693 on LeetCode and check those bits today!