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

Item	Meaning
Input	A positive integer n
Output	true if adjacent bits alternate, otherwise false
Constraint	1 <= n <= 2^31 - 1
Binary rule	No two adjacent bits may be equal

Example function shape:

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

Examples

Example 1:

n = 5

Binary:

101

Adjacent pairs:

Pair	Different?
1, 0	Yes
0, 1	Yes

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.

Metric	Value	Why
Time	O(w)	We scan the binary representation once
Space	O(w)	The binary string stores all bits

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:

Test	Binary	Expected	Why
5	101	true	Alternating
7	111	false	Adjacent 1s
11	1011	false	Ends with adjacent 1s
10	1010	true	Alternating
1	1	true	Single bit has no bad adjacent pair
2	10	true	Adjacent bits differ
3	11	false	Adjacent bits equal
21	10101	true	Alternating