Code Implementation

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = n & 1
        n = n >> 1
        while n:
            curr = n & 1
            if curr == prev:
                return False
            prev = curr
            n = n >> 1
        return True
    

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n = n >> 1;
        while (n) {
            int curr = n & 1;
            if (curr == prev) return false;
            prev = curr;
            n = n >> 1;
        }
        return true;
    }
};
    

class Solution {
    public boolean hasAlternatingBits(int n) {
        int prev = n & 1;
        n = n >> 1;
        while (n != 0) {
            int curr = n & 1;
            if (curr == prev) return false;
            prev = curr;
            n = n >> 1;
        }
        return true;
    }
}
    

var hasAlternatingBits = function(n) {
    let prev = n & 1;
    n = n >> 1;
    while (n) {
        let curr = n & 1;
        if (curr === prev) return false;
        prev = curr;
        n = n >> 1;
    }
    return true;
};
    

Problem Description

Given a positive integer n, determine whether its binary representation has alternating bits. Alternating bits mean that no two adjacent bits in the binary representation are the same; in other words, the bits alternate between 0 and 1 at every position.

For example, the number 5 (binary 101) has alternating bits, but 7 (binary 111) does not.

• You are given a single integer n.
• Return true if the binary representation of n has alternating bits, otherwise return false.
• There is only one valid answer for each input. No elements or values are reused.

Thought Process

When first approaching this problem, you might think of converting the number n to a binary string and checking each character to see if it alternates. This is a straightforward brute-force approach.

However, since we are working with bits, we can exploit bitwise operations to check the pattern more efficiently. The key insight is that we only need to compare each bit with its neighbor to ensure they are different. If at any position two adjacent bits are the same, the answer is false.

To do this efficiently, we can use bitwise AND and shift operations to extract and compare bits directly, which avoids the overhead of string conversion and is generally faster.

Solution Approach

• Step 1: Extract the last bit of n using n & 1. This gives us the least significant bit (rightmost bit) as our starting point.
• Step 2: Right shift n by 1 to move to the next bit.
• Step 3: In a loop, keep extracting the current last bit (using n & 1) and compare it to the previous bit.
• Step 4: If at any point the current bit is equal to the previous bit, return false because the bits are not alternating.
• Step 5: If the loop finishes without finding two equal adjacent bits, return true.

This approach leverages bitwise operations for efficiency. Bitwise AND (&) and right shift (>>) are both fast, constant-time operations. We use a variable to keep track of the previous bit and walk through the binary representation from right to left.

Example Walkthrough

Let's walk through the input n = 10. The binary representation of 10 is 1010.

1. Initialize prev = 0 (since 10 & 1 = 0), then right shift: n = 5.
2. Extract current bit: curr = 1 (5 & 1). Compare to prev = 0; they are different.
3. Set prev = 1, right shift: n = 2.
4. Extract current bit: curr = 0 (2 & 1). Compare to prev = 1; they are different.
5. Set prev = 0, right shift: n = 1.
6. Extract current bit: curr = 1 (1 & 1). Compare to prev = 0; they are different.
7. Set prev = 1, right shift: n = 0. Loop ends.

Since we never found two equal adjacent bits, we return true.

Time and Space Complexity

• Brute-force approach: If we convert n to a binary string, the time complexity is O(k), where k is the number of bits (up to 32 for a 32-bit integer). Space complexity is also O(k) due to the string.
• Optimized bitwise approach: The time complexity is O(k), since we examine each bit once. Space complexity is O(1), as we only use a few variables and do not allocate extra memory.

The optimized approach is both time and space efficient, making it suitable for large integers.

Summary

To solve the "Binary Number with Alternating Bits" problem, we leveraged bitwise operations to efficiently compare each adjacent bit in the binary representation of the input number. By avoiding string conversion and using only a few variables, the solution is both elegant and efficient, running in linear time relative to the number of bits and constant space. The key insight is to compare each bit with its neighbor using bitwise AND and shifts, stopping early if a repeated bit is found.