89. Gray Code — DSA Atlas

MediumBit ManipulationBit manipulation with a closed-form reflected Gray code formulaBinary-to-Gray transform (i XOR i>>1)

Gray Code

An n-bit Gray code sequence is a list of 2^n integers where every integer is in [0, 2^n - 1], the sequence starts at 0, each integer appears exactly once, adjacent integers differ in exactly one bit, and the first and last integers also differ in exactly one bit. Given n, return any valid n-bit Gray code sequence.

Open official problem prompt ↗

In plain English

Enumerate all 2^n binary numbers in an order where each step changes only a single bit, forming a cyclic single-bit-change sequence starting at 0.

Picture it like this

Turning the dials of a combination lock so that only one wheel clicks by one notch at a time, yet you still visit every possible combination exactly once.

Example

Input: n = 2
Output: [0, 1, 3, 2]
Why: 00 -> 01 -> 11 -> 10 each differ by one bit, and 10 -> 00 (wrap) also differs by one bit.

Constraints

1 <= n <= 16

Pattern lesson

See the pattern, then code

Binary-to-Gray transform (i XOR i>>1)

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. The i-th reflected Gray code value is i ^ (i >> 1). XORing an index with its own right-shift flips exactly the bits where adjacent indices' binary representations carry, guaranteeing single-bit transitions between consecutive terms.

New words, made simpleKnow these before the algorithm

Gray code: An ordering of binary numbers in which consecutive values differ in exactly one bit.
Reflected Gray code: The standard Gray code obtained by mirroring the sequence for n-1 bits; its i-th term is i ^ (i >> 1).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Recursive reflection

Correct and instructive but more code and bookkeeping than needed.

Build the (n)-bit sequence by taking the (n-1)-bit sequence, mirroring it, and prefixing 0s then 1s.

Time O(2^n)Space O(2^n)

Best choiceClosed-form XOR formula

One line, no recursion, provably a valid Gray code.

Directly output i ^ (i >> 1) for i in [0, 2^n).

Time O(2^n)Space O(2^n)

The rule we keep true

Invariant

For consecutive indices i and i+1, the values i^(i>>1) and (i+1)^((i+1)>>1) differ in exactly one bit position.

Why this is correct

Reasoning

Adding 1 to i flips a suffix of trailing 1s to 0 and sets the next bit. In the transform g(i)=i^(i>>1), all those internal carry flips cancel between the value and its shifted copy, leaving exactly one bit changed between g(i) and g(i+1). The wrap from the last value back to 0 also differs by one bit because 2^n-1 maps to a single high bit.

The algorithm in three movesSay these aloud before coding

1Loop i from 0 to 2^n - 1

i=0: 0^0 = 0

2For each i compute i ^ (i >> 1)

i=1: 1^0 = 1

3Append that value to the result list

i=2: 2^1 = 3

4Return the list

i=3: 3^1 = 2

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

0->000

1->011

2->112

3->103

1 · Read0 = 00

2 · Ask0 ^ (0>>1)?

3 · Update stateresult=[0]

4 · Result0

Key takeaway

Each index i maps to i ^ (i>>1), producing 0,1,3,2 with single-bit steps.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Formula over the full range
1 << n is 2^n; iterating i over that range and emitting i ^ (i >> 1) produces the entire reflected Gray code.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 1 returns [0, 1]
Largest n = 16 produces 65536 values
The sequence always begins with 0

Common beginner mistakes

Using arithmetic shift or wrong precedence — parenthesize (i >> 1)
Assuming the answer must be unique; LeetCode accepts any valid Gray code
Off-by-one in the range: it must be 2^n values, not 2^n - 1

Check your understanding

Why does i ^ (i >> 1) guarantee a single-bit change between consecutive terms?

Gray Code

Gray Code

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation