Gray Code
Gray Code is LeetCode 89 (Medium). Return any n-bit gray code sequence: a permutation of all 2ⁿ integers in [0, 2ⁿ − 1] where every consecutive pair, and the last and first pair, differ in exactly one bit.
With n up to 16 the output can hold 65,536 values, so the sequence has to be produced directly rather than searched for.
- 1 <= n <= 16
Intuition
Searching for a valid ordering — pick a value, then hunt for an unused one a single bit away — is backtracking over an exponential space, and it is unnecessary. There is a gray code formula.
The i-th gray code is i XOR (i >> 1). It works because i and i + 1 differ in a trailing run of bits: the lowest zero flips to one and every one below it flips to zero. XOR-ing each value with itself shifted right cancels all of those flips except one, so consecutive outputs always differ in a single bit.
The wraparound comes free: the last value differs from the first only in the top bit.
A closed form beats a search whenever the output is a complete enumeration with a structural rule. The tell here is that any valid sequence is accepted and every value must appear exactly once — that is a permutation to construct, not a space to explore.
Approach
Before reading on: write out the 3-bit sequence 0, 1, 3, 2, 6, 7, 5, 4 next to the plain binary counts 0..7 and compare them bit by bit. The relationship between the two columns is the entire solution. Aim for O(2ⁿ) with no recursion.
Two ways to solve it
Use this when you just need the sequence out.
- Directness: each value computed from its index alone.
- Simplicity: one loop, one expression, no state.
- Independence: entry i needs nothing from entry i − 1.
Both methods are O(2ⁿ), so this one wins on having no list surgery at all.
Reach for this when you want the structure to be visible.
- Construction: builds the n-bit answer from the (n − 1)-bit one.
- Insight: the mirror seam is why the single-bit rule survives.
- Cost: repeated reversal and reallocation of the list.
It is the better explanation and the worse implementation.
The XOR formula wins because each value depends only on its own index, so nothing is reversed or rebuilt. The steps, code and live run below follow it; the reflect-and-prefix construction appears further down, where the structure of the sequence is easier to see.
Produce the sequence instead of searching for it
There are 2ⁿ values to emit, and any valid n-bit gray code sequence is accepted. A closed form gives the i-th value directly, so a single loop from 0 to 2ⁿ − 1 builds the whole answer with no recursion, no backtracking and no bookkeeping of which values are still unused.
Apply i XOR (i >> 1)
For each i, append i ^ (i >> 1). Two details decide whether it works:
- Shift right, not left: a left shift produces values outside the n-bit range and destroys the single-bit property.
- Keep the parentheses:
^binds looser than>>in some languages but not all, so spell the order out.
Count 2ⁿ values, not n
The loop bound is 1 << n, the number of n-bit values. Using n itself returns a truncated prefix that happens to look plausible for small inputs, which is why this bug survives a quick test.
Gray Code solution in Python | C++ | Java
i ^ (i >> 1), so each value can be written down from its index alone.i = 0 the expression gives 0, so the sequence starts at zero. Every later value is computed the same way, with no reference to this one.1 ^ 0 = 1. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.2 ^ 1 = 3. Exactly one bit differs from the previous value — bit 1 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.3 ^ 1 = 2. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.2 and 0 differ only in the top bit. That wraparound is part of the requirement and easy to miss when checking by hand.i ^ (i >> 1), so each value can be written down from its index alone.i = 0 the expression gives 0, so the sequence starts at zero. Every later value is computed the same way, with no reference to this one.1 ^ 0 = 1. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.2 ^ 1 = 3. Exactly one bit differs from the previous value — bit 1 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.3 ^ 1 = 2. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.4 ^ 2 = 6. Exactly one bit differs from the previous value — bit 2 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.5 ^ 2 = 7. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.6 ^ 3 = 5. Exactly one bit differs from the previous value — bit 1 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.7 ^ 3 = 4. Exactly one bit differs from the previous value — bit 0 — which is what XOR-ing with the shifted copy guarantees, not a coincidence of this input.4 and 0 differ only in the top bit. That wraparound is part of the requirement and easy to miss when checking by hand.Reflect and prefix
Start from [0] and grow one bit at a time. For each new bit, append the list so far in reverse order with that bit set. Reversing is what keeps the seam valid: the two values meeting at the mirror point are identical except for the bit just added.
Common pitfalls
Building it by mirroring the previous sequence
res = [0]
for i in range(n):
res += [x | (1 << i) for x in reversed(res)]for i in range(total):
result.append(i ^ (i >> 1))The mirroring construction is correct and shows where gray code comes from, but it repeatedly reverses and reallocates the list it is building. The formula computes each entry independently in O(1), with no dependence on the entries before it.
Shifting the wrong way
result.append(i ^ (i << 1))
result.append(i ^ (i >> 1))
Left-shifting produces values outside the n-bit range and breaks the single-bit-change property. The identity requires XOR with the value shifted right by one.
Computing the wrong sequence length
total = n
total = 1 << n
A Gray code of n bits enumerates all 2^n values, not n of them. 1 << n is the count; using n returns a truncated prefix.
Edge cases
The loop runs twice and returns [0, 1], the smallest real sequence: one bit toggling, and the wraparound back to 0 also flips that one bit.
The last value and the first differ only in the top bit, which the formula guarantees. It is easy to forget when checking your own output by hand.
65,536 values, each one constant-time expression, so the formula scales without any extra bookkeeping.