Leetcode – Binary Number with Alternating Bits Solution in Python

Spread the love

Introduction

Programming problems that involve binary numbers can be challenging but also fun to solve, providing the opportunity to delve deep into the fundamental workings of computers. This article will explore one such problem from Leetcode – the ‘Binary Number with Alternating Bits’ problem. We’ll discuss various approaches using Python and the underlying concepts in detail.

Problem Statement

Here’s the problem as given on LeetCode:

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

For example, for input 5, the output should be True. This is because 5 in binary is 101, which has alternating 1s and 0s.

But for input 7, the output should be False. This is because 7 in binary is 111, which does not have alternating bits.

Understanding the Problem

Before we dive into the solution, it’s important to understand what the problem is asking.

We need to determine whether a given integer, when represented in binary, has alternating 1s and 0s. In other words, no two consecutive bits in the binary representation of the number are the same.

Solution Using Bit Manipulation

Python has a built-in function, bin(), that can convert an integer into a binary string. We can use this function to get the binary representation of the number and then simply iterate through the string to check for any two consecutive bits that are the same.

Here is a Python function that solves the problem:

def hasAlternatingBits(n):
    # Convert to binary and remove the "0b" prefix
    binary = bin(n)[2:]

    # Iterate through the binary string
    for i in range(len(binary) - 1):
        # If two consecutive bits are the same, return False
        if binary[i] == binary[i+1]:
            return False

    # If no two consecutive bits are the same, return True
    return True

While this solution is straightforward and works, we can also solve the problem using bit manipulation, which is a more optimal and elegant solution.

Optimal Solution

The optimal solution to this problem involves using bitwise operators.

Here’s the intuition: If a number n is a binary number with alternating bits, then n >> 1 is n with all bits shifted to the right by one place, and n ^ (n >> 1) should give us a number with all bits set to 1.

Here’s the step-by-step breakdown:

  1. We first shift the bits of n one place to the right to get n >> 1.
  2. We then perform a bitwise XOR operation between n and n >> 1.
  3. If n has alternating bits, then all the bits in n ^ (n >> 1) will be set to 1.
  4. To check if all the bits in a number are set to 1, we can add 1 to the number and perform a bitwise AND operation between the number and the number + 1. If the result is 0, then all bits in the original number were set to 1.

Here is the Python function implementing the above steps:

def hasAlternatingBits(n):
    n ^= n >> 1
    return n & (n + 1) == 0

This function first calculates n ^ (n >> 1), and then checks if the result n & (n + 1) is equal to 0. If it is, the function returns True, meaning the original number n has alternating bits. Otherwise, it returns False.

Testing the Solution

Let’s test the function with some inputs:

print(hasAlternatingBits(5))  # Returns True
print(hasAlternatingBits(7))  # Returns False
print(hasAlternatingBits(11))  # Returns False
print(hasAlternatingBits(10))  # Returns True

The function should return True for inputs 5 and 10, and False for inputs 7 and 11. This matches our expectation, verifying the correctness of our function.

Conclusion

Solving the ‘Binary Number with Alternating Bits’ problem on LeetCode not only requires knowledge of Python but also a good understanding of binary numbers and bitwise operations. This problem is a good example of how bitwise operations can lead to efficient and elegant solutions. Understanding how bitwise operators work can be extremely beneficial, especially when dealing with problems related to binary numbers or bit manipulation.

Leave a Reply