# 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:

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

## Examples

Example 1:

```python
n = 5
```

Binary:

```text
101
```

Adjacent pairs:

| Pair | Different? |
|---|---:|
| `1, 0` | Yes |
| `0, 1` | Yes |

Answer:

```python
True
```

Example 2:

```python
n = 7
```

Binary:

```text
111
```

The first two adjacent bits are both `1`.

Answer:

```python
False
```

Example 3:

```python
n = 10
```

Binary:

```text
1010
```

Every adjacent pair is different.

Answer:

```python
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.

```python
bin(n)
```

returns a string like:

```text
0b101
```

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

```python
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

```python
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:

```python
bits = bin(n)[2:]
```

For example:

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

The loop compares each bit with the previous bit:

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

If two adjacent bits are equal:

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

the pattern is not alternating.

If no equal adjacent bits are found:

```python
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.

```python
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:

```python
n & 1
```

extracts the last bit.

And:

```python
n >>= 1
```

removes the last bit.

## Testing

```python
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 `1`s |
| `11` | `1011` | `false` | Ends with adjacent `1`s |
| `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 |