Problem Description

You are given a positive integer n. Your task is to determine whether this number has alternating bits in its binary representation. A number has alternating bits if every two adjacent bits (consecutive bits) in its binary form have different values - meaning no two adjacent bits are the same.

For example:

• The number 5 in binary is 101. Reading from right to left, we have bits: 1, 0, 1. Each adjacent pair (1-0 and 0-1) has different values, so it has alternating bits.
• The number 7 in binary is 111. All adjacent bits are the same (1-1 and 1-1), so it does not have alternating bits.
• The number 10 in binary is 1010. Each adjacent pair (0-1, 1-0, 0-1) has different values, so it has alternating bits.

The solution iterates through each bit of the number from right to left using bitwise operations. It extracts the current bit using n & 1, compares it with the previous bit, and returns False if any two adjacent bits are found to be the same. The number is right-shifted by 1 position (n >>= 1) in each iteration to process the next bit. If all adjacent bits are different, the function returns True.

Intuition

To check if a number has alternating bits, we need to examine its binary representation bit by bit. The key insight is that we can process the bits sequentially from right to left (least significant to most significant) and compare each bit with its neighbor.

Think of it like walking through a sequence and checking if the pattern alternates. If we're looking at binary digits, we want to see patterns like 1010... or 0101..., never 11... or 00....

The natural approach is to:

1. Extract the rightmost bit of the number
2. Compare it with the next bit
3. If they're the same, we know the bits don't alternate
4. If they're different, continue checking the next pair

We can efficiently extract bits using bitwise operations. The expression n & 1 gives us the rightmost bit (it's 1 if the bit is 1, and 0 if the bit is 0). After checking a bit, we can shift the entire number right by one position using n >>= 1, which effectively removes the rightmost bit and brings the next bit into position for checking.

By keeping track of the previous bit we examined and comparing it with the current bit in each iteration, we can detect if any two adjacent bits are the same. If we find even one pair of adjacent bits that match, we immediately know the number doesn't have alternating bits. If we process all bits without finding matching adjacent bits, then the number has alternating bits.

Solution Approach

The implementation uses a bit manipulation approach to check each bit of the number sequentially:

1. Initialize tracking variable: We start with prev = -1 to store the previous bit. We use -1 as the initial value since it's different from both 0 and 1, ensuring the first bit comparison always passes.

2. Process bits from right to left: We enter a while n: loop that continues as long as n is not zero.

3. Extract current bit: In each iteration, we get the rightmost bit using curr = n & 1. The bitwise AND operation with 1 masks all bits except the rightmost one, giving us either 0 or 1.

4. Check for alternating pattern: We compare curr with prev. If they're equal (prev == curr), it means we found two adjacent bits with the same value, so we immediately return False.

5. Update for next iteration: If the bits are different, we:

   • Update prev = curr to remember the current bit for the next comparison
   • Right shift the number using n >>= 1 to remove the processed bit and bring the next bit into the rightmost position

6. Return result: If we exit the loop without finding any matching adjacent bits, we return True.

The algorithm has a time complexity of O(log n) since we process each bit of the number once, and the number of bits in n is proportional to log n. The space complexity is O(1) as we only use a constant amount of extra space for the prev and curr variables.

Example Walkthrough

Let's walk through the solution with n = 10 (binary: 1010).

Initial state:

• n = 10 (binary: 1010)
• prev = -1 (initial value, different from 0 and 1)

Iteration 1:

• Extract rightmost bit: curr = 10 & 1 = 0 (binary: 1010 & 0001 = 0000)
• Compare: prev (-1) ≠ curr (0), so continue
• Update: prev = 0
• Right shift: n = 10 >> 1 = 5 (binary: 1010 becomes 0101)

Iteration 2:

• Extract rightmost bit: curr = 5 & 1 = 1 (binary: 0101 & 0001 = 0001)
• Compare: prev (0) ≠ curr (1), so continue
• Update: prev = 1
• Right shift: n = 5 >> 1 = 2 (binary: 0101 becomes 0010)

Iteration 3:

• Extract rightmost bit: curr = 2 & 1 = 0 (binary: 0010 & 0001 = 0000)
• Compare: prev (1) ≠ curr (0), so continue
• Update: prev = 0
• Right shift: n = 2 >> 1 = 1 (binary: 0010 becomes 0001)

Iteration 4:

• Extract rightmost bit: curr = 1 & 1 = 1 (binary: 0001 & 0001 = 0001)
• Compare: prev (0) ≠ curr (1), so continue
• Update: prev = 1
• Right shift: n = 1 >> 1 = 0 (binary: 0001 becomes 0000)

End:

• n = 0, exit loop
• Return True (all adjacent bits were different)

The bits we examined in order were: 0, 1, 0, 1 - each adjacent pair (0-1, 1-0, 0-1) had different values, confirming that 10 has alternating bits.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n) where n is the input integer. The algorithm iterates through each bit of the binary representation of n. Since an integer n has approximately log₂(n) bits, the while loop executes O(log n) times. In each iteration, we perform constant time operations: bitwise AND (n & 1), comparison, assignment, and right shift (n >>= 1).

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size. We only maintain two variables: prev to store the previous bit value and curr to store the current bit value. These variables don't grow with the input size, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initial Value for Previous Bit

A common mistake is initializing previous_bit to 0 or 1 instead of -1 (or another invalid value). This can cause incorrect results for certain inputs.

Problematic Code:

def hasAlternatingBits(self, n: int) -> bool:
    previous_bit = 0  # Wrong! Could match the first bit
    while n > 0:
        current_bit = n & 1
        if previous_bit == current_bit:
            return False
        previous_bit = current_bit
        n >>= 1
    return True

Issue: If n = 2 (binary: 10), the first bit is 0. With previous_bit = 0, the function incorrectly returns False even though 10 has alternating bits.

Solution: Always initialize previous_bit to -1 or handle the first bit separately:

# Option 1: Use -1 as initial value
previous_bit = -1

# Option 2: Handle first bit separately
previous_bit = n & 1
n >>= 1
while n > 0:
    current_bit = n & 1
    if previous_bit == current_bit:
        return False
    previous_bit = current_bit
    n >>= 1
return True

2. Using XOR Without Proper Validation

Some might try to optimize using XOR to check all bits at once, but this can miss important cases.

Problematic Code:

def hasAlternatingBits(self, n: int) -> bool:
    # Shift and XOR approach
    temp = n ^ (n >> 1)
    # Wrong check - doesn't validate all bits are 1
    return temp > 0  

Issue: This doesn't properly verify that temp has all bits set to 1. For example, n = 4 (binary: 100) gives temp = 6 (binary: 110), which is positive but doesn't represent alternating bits.

Solution: If using the XOR approach, validate that the result has all bits set:

def hasAlternatingBits(self, n: int) -> bool:
    temp = n ^ (n >> 1)
    # Check if temp has all bits set to 1
    # Adding 1 to all 1s gives a power of 2
    return (temp & (temp + 1)) == 0

3. Forgetting Edge Cases

Not considering single-bit numbers or the smallest inputs.

Issue: While the given solution handles these correctly, modifications might break edge cases like n = 1 (binary: 1) which should return True.

Solution: Always test with minimal inputs:

• n = 1 (binary: 1) → True
• n = 2 (binary: 10) → True
• n = 3 (binary: 11) → False