algoadvance

Given a positive integer n, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Clarifying Questions

  1. Range of input: Is there a constraint on how large the integer n can be?
    • Assume n can be any positive integer within the typical 32-bit signed integer range.
  2. Output format: Should the output be a boolean indicating whether the integer has alternating bits?
    • Yes, the output should be True if the integer has alternating bits, otherwise False.

Strategy

  1. Binary Representation: Convert the integer n to its binary representation.
  2. Alternating Bits Check:
    • Iterate through the binary string, comparing each bit with the next bit.
    • If any two consecutive bits are the same, return False.
    • If the loop completes without finding identical consecutive bits, return True.

Detailed Steps

  1. Convert the integer n to a binary string using Python’s built-in bin() function and strip off the '0b' prefix.
  2. Loop through the binary string and compare each bit to the next bit.
  3. If any bit matches the next bit, return False.
  4. If the loop completes successfully, return True.

Code

def hasAlternatingBits(n: int) -> bool:
    # Get the binary representation of the number, without the '0b' prefix
    binary_str = bin(n)[2:]
    
    # Loop through the binary string
    for i in range(len(binary_str) - 1):
        # Check if the current bit is the same as the next bit
        if binary_str[i] == binary_str[i + 1]:
            return False
    
    return True

# Example usage:
print(hasAlternatingBits(5))  # True, binary: '101'
print(hasAlternatingBits(7))  # False, binary: '111'
print(hasAlternatingBits(11)) # False, binary: '1011'
print(hasAlternatingBits(10)) # True, binary: '1010'

Time Complexity

The overall time complexity is dominated by these operations and can be considered (O(\log n)).

Try our interview co-pilot at AlgoAdvance.com