Gray Code
Generate an n-bit Gray code sequence where every consecutive pair, including the wraparound, differs by exactly one bit.
Open on LeetCode ↗Intuition
The trap is trying to build the sequence by searching for a next value that differs from the current one by a single bit -- that's backtracking over an exponential space of 2^n candidates at each step, and it's completely unnecessary. There's a closed form: the i-th value in the sequence is simply i XOR (i >> 1). This formula guarantees the one-bit-difference property automatically, because XORing with a right-shifted copy of yourself only ever toggles one bit as i increments by one in binary -- you don't need to verify it, it falls out of the math. The invariant worth trusting: generate i from 0 to 2^n - 1 in plain counting order, apply the formula, and the single-bit-difference property (including the wrap from the last code back to 0) is guaranteed for free.
The closed form i ^ (i >> 1) generates the reflected binary code directly — no recursion, no mirroring of a previous list. It works because XOR-ing with the shifted value flips exactly one bit between consecutive integers, which is precisely the Gray code property.
Approach
Compute the total count
The sequence has exactly 2^n entries for n bits, computed as 1 << n. This bounds the loop and requires no recursive exploration.
Apply the closed-form formula
For each i from 0 to 2^n - 1, compute i ^ (i >> 1) and append it to the result list. The right-shift-then-XOR pattern is what converts a normal binary counter into reflected binary (Gray) code.
Return the sequence directly
No backtracking, no adjacency checking, no undo -- the formula-generated list already satisfies the required property between every consecutive pair and between the last and first elements.
Solution & live demo
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 reallocates and reverses. The formula computes each entry independently in O(1).
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
1 << 0 = 1, loop runs once for i=0, returns [0]
returns [0, 1], the smallest real Gray code toggle
guaranteed by the formula's structure, no explicit check needed
formula scales identically, still O(2^n) time with no extra bookkeeping