# LeetCode 89: Gray Code

## Problem Restatement

We are given an integer `n`.

We need to return any valid `n`-bit Gray code sequence.

A valid Gray code sequence has these rules:

| Rule | Meaning |
|---|---|
| Length | The sequence contains `2^n` integers |
| Range | Every integer is between `0` and `2^n - 1` |
| Start | The first integer must be `0` |
| No duplicates | Each integer appears at most once |
| Adjacent rule | Adjacent integers differ by exactly one bit |
| Circular rule | The first and last integers also differ by exactly one bit |

The official constraints are `1 <= n <= 16`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | A valid `n`-bit Gray code sequence |
| Sequence length | `2^n` |
| First value | Must be `0` |
| Valid transition | Consecutive values differ by one bit |

Function shape:

```python
class Solution:
    def grayCode(self, n: int) -> list[int]:
        ...
```

## Examples

Example 1:

```python
n = 2
```

One valid answer is:

```python
[0, 1, 3, 2]
```

In binary:

```python
0 -> 00
1 -> 01
3 -> 11
2 -> 10
```

Check adjacent differences:

```python
00 -> 01  differs by 1 bit
01 -> 11  differs by 1 bit
11 -> 10  differs by 1 bit
10 -> 00  differs by 1 bit
```

Example 2:

```python
n = 1
```

A valid answer is:

```python
[0, 1]
```

In binary:

```python
0 -> 0
1 -> 1
```

The two values differ by one bit.

## First Thought: Build the Sequence by Reflection

A common way to construct Gray code is reflection.

Start with the 1-bit sequence:

```python
[0, 1]
```

For 2 bits:

1. Keep the old sequence with leading `0`.
2. Reflect the old sequence and add leading `1`.

```python
00
01
11
10
```

That gives:

```python
[0, 1, 3, 2]
```

For 3 bits, reflect the 2-bit sequence:

```python
000
001
011
010
110
111
101
100
```

That gives:

```python
[0, 1, 3, 2, 6, 7, 5, 4]
```

This is a good construction, but there is an even shorter formula.

## Key Insight

The `i`-th Gray code value can be computed directly from `i`.

The formula is:

```python
gray = i ^ (i >> 1)
```

Here:

| Operation | Meaning |
|---|---|
| `>> 1` | Shift bits one position to the right |
| `^` | XOR two bit patterns |

So the full sequence is:

```python
[i ^ (i >> 1) for i in range(1 << n)]
```

The expression:

```python
1 << n
```

means:

```python
2^n
```

## Why the Formula Works

Write `i` in binary.

The Gray code bit at each position records whether the binary bit changed from the previous higher bit.

For example, with 3-bit numbers:

```python
i = 5
binary i = 101
```

Shift right by one:

```python
i >> 1 = 010
```

XOR them:

```python
101
010
---
111
```

So:

```python
gray(5) = 7
```

This formula creates an ordering where moving from `i` to `i + 1` changes exactly one Gray-code bit.

The reason is that consecutive binary numbers change a suffix of bits, but the XOR-with-shift transformation compresses that carry change into one Gray-code bit.

## Algorithm

Compute all Gray code values directly.

1. Let `total = 1 << n`.
2. Create an empty answer list.
3. For each `i` from `0` to `total - 1`, append `i ^ (i >> 1)`.
4. Return the answer.

## Walkthrough

Use:

```python
n = 3
```

Then:

```python
total = 1 << 3 = 8
```

Now compute each value:

| `i` | Binary `i` | `i >> 1` | Gray binary | Gray decimal |
|---:|---|---|---|---:|
| `0` | `000` | `000` | `000` | `0` |
| `1` | `001` | `000` | `001` | `1` |
| `2` | `010` | `001` | `011` | `3` |
| `3` | `011` | `001` | `010` | `2` |
| `4` | `100` | `010` | `110` | `6` |
| `5` | `101` | `010` | `111` | `7` |
| `6` | `110` | `011` | `101` | `5` |
| `7` | `111` | `011` | `100` | `4` |

The result is:

```python
[0, 1, 3, 2, 6, 7, 5, 4]
```

## Correctness

The algorithm returns exactly `2^n` values because it iterates over every integer `i` from `0` to `2^n - 1`.

The first value is:

```python
0 ^ (0 >> 1) = 0
```

So the sequence starts with `0`.

Every returned value is in the range `[0, 2^n - 1]` because `i` has at most `n` bits, `i >> 1` has at most `n - 1` bits, and XOR cannot create a bit beyond the highest bit of `i`.

The mapping:

```python
i -> i ^ (i >> 1)
```

is one-to-one over all `n`-bit integers. Gray code can be decoded back to the original binary number by repeatedly XORing prefix bits, so two different `i` values cannot produce the same Gray value.

Finally, consecutive integers `i` and `i + 1` differ by a carry pattern in binary. The formula `i ^ (i >> 1)` converts that carry pattern into a change in exactly one output bit. Therefore, adjacent Gray code values differ by exactly one bit.

The last and first values also differ by one bit. The first value is `0`. The last value is:

```python
(2^n - 1) ^ ((2^n - 1) >> 1)
```

For `n` bits, `2^n - 1` is all ones. Shifting right gives a leading zero followed by `n - 1` ones. XOR produces only the highest bit set:

```python
100...0
```

That differs from `0` by exactly one bit.

Therefore, the returned sequence satisfies all Gray code rules.

## Complexity

Let:

```python
N = 2^n
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(2^n)` | We generate exactly `2^n` values |
| Space | `O(2^n)` | The output list stores `2^n` values |
| Extra space | `O(1)` | Apart from the output, only loop variables are used |

## Implementation

```python
class Solution:
    def grayCode(self, n: int) -> list[int]:
        ans = []

        for i in range(1 << n):
            ans.append(i ^ (i >> 1))

        return ans
```

A shorter version:

```python
class Solution:
    def grayCode(self, n: int) -> list[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]
```

## Code Explanation

The number of required values is:

```python
1 << n
```

This equals `2^n`.

For each position `i`, compute its Gray code value:

```python
i ^ (i >> 1)
```

Then append it to the answer.

The first value is automatically `0`.

The generated sequence satisfies the adjacent one-bit difference rule.

## Testing

```python
def differs_by_one_bit(a, b):
    x = a ^ b
    return x != 0 and (x & (x - 1)) == 0

def check(n):
    s = Solution()
    result = s.grayCode(n)

    assert len(result) == 1 << n
    assert result[0] == 0
    assert len(set(result)) == len(result)

    for value in result:
        assert 0 <= value < (1 << n)

    for i in range(len(result) - 1):
        assert differs_by_one_bit(result[i], result[i + 1])

    assert differs_by_one_bit(result[-1], result[0])

def run_tests():
    check(1)
    check(2)
    check(3)
    check(4)

    assert Solution().grayCode(2) == [0, 1, 3, 2]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Smallest valid input |
| `n = 2` | Main small example |
| `n = 3` | Checks longer reflected pattern |
| `n = 4` | Checks general generation |
| Unique values | Confirms no duplicates |
| Range check | Confirms every value fits in `n` bits |
| Adjacent bit check | Confirms Gray code property |
| Last-to-first check | Confirms circular property |