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:

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:

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

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:

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:

[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

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

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:

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