Domain 1EasyCORE

Binary Number with Alternating Bits

The problem requires checking whether a given positive integer has alternating bits in its binary representation. In other words, no two adjacent bits should be the same. The input is a single positive integer `n`, and the output is a boolean indicating whether the condition is met.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

693. Binary Number with Alternating Bits

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 0
Acceptance rate: 60.0%


Problem Breakdown

The problem requires checking whether a given positive integer has alternating bits in its binary representation. In other words, no two adjacent bits should be the same. The input is a single positive integer n, and the output is a boolean indicating whether the condition is met.

Inputs:

  • A positive integer n (1 <= n <= 2^31 - 1)

Outputs:

  • Boolean value (true or false)

Implicit Constraints:

  • The input is always a positive integer, so we don’t need to handle negative numbers or zero.
  • The binary representation of the number should be checked for alternating bits.

Intuition

A brute-force approach would involve converting the integer to its binary string representation and then iterating through the string to check if adjacent bits are different. However, this approach is inefficient in terms of both time and space complexity because it involves string operations and multiple iterations.

A more efficient approach leverages bit manipulation. The key insight is that if we shift the number one position to the right and XOR it with the original number, all bits should be set to 1 if the original number has alternating bits. For example, for n = 5 (binary 101), shifting right gives 010, and XORing 101 with 010 results in 111. Adding 1 to this result should make all bits set to 0 if the number has alternating bits.

Approach

  1. Bit Manipulation Insight:

    • Shift the number one position to the right.
    • XOR the shifted number with the original number.
    • Add 1 to the result of the XOR operation.
    • Check if the result is a power of two (i.e., it has exactly one bit set).
  2. Algorithm Steps:

    • Perform the bitwise operations as described above.
    • Use a helper function or a known method to check if a number is a power of two.

Complexity Analysis

  • Time Complexity: O(1) because the operations involve a fixed number of bitwise operations and comparisons.
  • Space Complexity: O(1) because we are using a constant amount of extra space.

Solution

def hasAlternatingBits(n: int) -> bool:
    # Shift right by 1 and XOR with original number
    shifted_xor = n ^ (n >> 1)
    
    # Add 1 to the result
    incremented_result = shifted_xor + 1
    
    # Check if the result is a power of two
    return incremented_result & (incremented_result - 1) == 0 and incremented_result != 0

# Example usage:
print(hasAlternatingBits(5))  # Output: True
print(hasAlternatingBits(7))  # Output: False
print(hasAlternatingBits(11)) # Output: False
print(hasAlternatingBits(10)) # Output: True
print(hasAlternatingBits(3))  # Output: False

Edge Cases Handled

  • Single-bit numbers: The algorithm correctly handles single-bit numbers like n = 1 (binary 1) and n = 2 (binary 10).
  • Maximum value: The algorithm works for the maximum possible input, n = 2^31 - 1, which has alternating bits.
  • Numbers with all identical bits: Numbers like n = 7 (binary 111) are correctly identified as not having alternating bits.