Binary Number With Alternating Bits - Leetcode Solution

Problem Statement:

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

Example 1:

Input: 5 Output: True Explanation: The binary representation of 5 is: 101 Example 2:

Input: 7 Output: False Explanation: The binary representation of 7 is: 111. Example 3:

Input: 11 Output: False Explanation: The binary representation of 11 is: 1011. Example 4:

Input: 10 Output: True Explanation: The binary representation of 10 is: 1010.

Solution:

To solve this problem, we need to check whether all adjacent bits in the binary representation of the given number are different or not. We can do this by using the bitwise operations.

1. Firstly, we need to convert the given integer into its binary representation. We can do this by repeatedly dividing the given number by 2 and noting down the remainder.

2. Once we have the binary representation, we can use a loop to iterate through all the bits in the number. We can do this by using the bitwise operators.

3. We check the current bit and the previous bit using the XOR operator. If the result is 1, then the bits are different. If the result is 0, then the bits are the same.

4. If we find any two adjacent bits that are the same, we can return False. Else, we can return True.

Pseudo Code:

1. Convert the given integer to binary representation
   • Initialize an empty string to store the binary representation
   • Repeatedly divide the given number by 2 and note down the remainder
   • Append the remainder to the binary representation string
2. Initialize a previous bit variable with -1
3. Loop through all the bits in the binary representation
   • If the previous bit is not -1, check the current bit and the previous bit using XOR
     • If the result is 0, return False
   • Update the previous bit with the current bit
4. If the loop completes successfully, return True

Python Code:

class Solution: def hasAlternatingBits(self, n: int) -> bool:

    # Convert the given number to binary representation
    binary = ""
    while n > 0:
        remainder = n % 2
        binary = str(remainder) + binary
        n //= 2
    
    # Check if adjacent bits are different
    previous_bit = -1
    for bit in binary:
        current_bit = int(bit)
        if previous_bit != -1:
            if current_bit ^ previous_bit == 0:
                return False
        previous_bit = current_bit
    
    return True

Time Complexity: O(log n) - We need to perform log n divisions to convert the given number to its binary representation.

Space Complexity: O(log n) - We need to store the binary representation of the given number in a string. The length of this string is log n.

1