LeetCode 693: Binary Number with Alternating Bits

Problem Restatement

We are given a positive integer n.

We need to check whether its binary representation has alternating bits.

That means every pair of adjacent bits must be different. The official statement says two adjacent bits should always have different values. For example, 5 is valid because its binary representation is 101, while 7 is invalid because its binary representation is 111.

Input and Output

Example function shape:

def hasAlternatingBits(n: int) -> bool:
    ...

Examples

Example 1:

n = 5

Binary:

101

Adjacent pairs:

Answer:

True

Example 2:

n = 7

Binary:

111

The first two adjacent bits are both 1.

Answer:

False

Example 3:

n = 10

Binary:

1010

Every adjacent pair is different.

Answer:

True

First Thought: Convert to Binary String

The simplest solution is to convert n to its binary representation as a string.

Then check adjacent characters.

bin(n)

returns a string like:

0b101

The first two characters are the prefix 0b, so we remove them with:

bin(n)[2:]

Then scan the string.

Algorithm

1. Convert n to a binary string.
2. For each index i from 1 to the end:
   • If bits[i] == bits[i - 1], return False.
3. If no equal adjacent pair is found, return True.

Correctness

The binary string contains the bits of n in order from most significant to least significant.

The algorithm checks every adjacent pair in that string.

If it finds two equal adjacent bits, then the binary representation does not alternate, so returning False is correct.

If the loop finishes, every adjacent pair has different bits. That is exactly the definition of alternating bits, so returning True is correct.

Complexity

Let w be the number of bits in n.

Since n <= 2^31 - 1, w <= 31, so this is effectively constant for this problem.

Implementation

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        bits = bin(n)[2:]

        for i in range(1, len(bits)):
            if bits[i] == bits[i - 1]:
                return False

        return True

Code Explanation

This line converts the number into binary form:

bits = bin(n)[2:]

For example:

bin(10)[2:] == "1010"

The loop compares each bit with the previous bit:

for i in range(1, len(bits)):

If two adjacent bits are equal:

if bits[i] == bits[i - 1]:
    return False

the pattern is not alternating.

If no equal adjacent bits are found:

return True

then the number has alternating bits.

Bit Manipulation Version

We can also avoid creating a string.

Read the bits from right to left.

Store the previous bit, then compare it with the next bit.

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        previous = n & 1
        n >>= 1

        while n:
            current = n & 1

            if current == previous:
                return False

            previous = current
            n >>= 1

        return True

Here:

n & 1

extracts the last bit.

And:

n >>= 1

removes the last bit.

Testing

def run_tests():
    s = Solution()

    assert s.hasAlternatingBits(5) is True
    assert s.hasAlternatingBits(7) is False
    assert s.hasAlternatingBits(11) is False
    assert s.hasAlternatingBits(10) is True

    assert s.hasAlternatingBits(1) is True
    assert s.hasAlternatingBits(2) is True
    assert s.hasAlternatingBits(3) is False
    assert s.hasAlternatingBits(21) is True

    print("all tests passed")

run_tests()

Test meaning: