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:

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

Input and Output

Function shape:

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

Examples

Example 1:

n = 2

One valid answer is:

[0, 1, 3, 2]

In binary:

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

Check adjacent differences:

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:

n = 1

A valid answer is:

[0, 1]

In binary:

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:

[0, 1]

For 2 bits:

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

00
01
11
10

That gives:

[0, 1, 3, 2]

For 3 bits, reflect the 2-bit sequence:

000
001
011
010
110
111
101
100

That gives:

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

gray = i ^ (i >> 1)

Here:

So the full sequence is:

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

The expression:

1 << n

means:

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:

i = 5
binary i = 101

Shift right by one:

i >> 1 = 010

XOR them:

101
010
---
111

So:

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:

n = 3

Then:

total = 1 << 3 = 8

Now compute each value:

The result is:

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

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:

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:

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

100...0

That differs from 0 by exactly one bit.

Therefore, the returned sequence satisfies all Gray code rules.

Complexity

Let:

N = 2^n

Implementation

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:

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:

1 << n

This equals 2^n.

For each position i, compute its Gray code value:

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

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: