Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Whether adjacent bits differ is unchanged when we inspect them in reverse order. Reading from the least significant bit lets us test every neighboring pair with only the previously seen bit. Leading zeros outside the number's representation must not be included.

Approach

Initialize the previous bit to a sentinel distinct from zero and one.
While n is nonzero, extract its lowest bit using the remainder modulo two. Return false if it equals the previous bit.
Remember the bit and shift n right to remove it.
Return true after all significant bits pass. A one-bit number is valid because there is no adjacent pair to violate the rule.

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

        while n:
            if n % 2 == prev:
                return False
            prev = n % 2
            n >>= 1

        return True

Complexity analysis

The loop examines one bit per iteration, so it uses O(log n) time and O(1) auxiliary space.