Gray Code — The XOR Shift Bit Trick That Generates the Sequence in O(1)

Problem Statement#

An n-bit Gray code sequence is a sequence of 2^n integers where:

• Every integer is in [0, 2^n - 1].
• The first integer is 0.
• Each consecutive pair (and the last/first pair, cyclically) differs by exactly one bit.
• Every integer appears exactly once.

Given an integer n, return any valid n-bit Gray code sequence.

Constraints:

• 1 <= n <= 16

Examples:

Input:  n = 2
Output: [0, 1, 3, 2]
Binary: [00, 01, 11, 10]   (each pair differs by one bit; 10 -> 00 also differs by one)
 
Input:  n = 1
Output: [0, 1]
 
Input:  n = 3
Output: [0, 1, 3, 2, 6, 7, 5, 4]
Binary: [000, 001, 011, 010, 110, 111, 101, 100]

Why This Problem Matters#

Gray codes power rotary encoders, error-tolerant counters, Karnaugh maps, and even genetic algorithms — flipping one bit at a time prevents transient miscounts when sensors sample mid-transition. From an interview lens, this question tests whether you reach for bit manipulation instead of recursion or backtracking. Google, Apple, and Amazon love it because the elegant solution is a single line of XOR — and most candidates first reach for a 30-line backtracking attempt.

The Core Insight (the bit-trick)#

The magic identity is:

gray(i) = i XOR (i >> 1)

Why does this work? Take any two consecutive integers i and i+1. Adding 1 flips a trailing run of bits — for instance, 0011 + 1 = 0100 flips three trailing bits. After XOR-ing with the right-shifted version, all but the highest of those flipped bits cancel out, leaving exactly one bit difference between gray(i) and gray(i+1).

Mechanically, the formula:

• Keeps the most significant bit of i unchanged.
• Replaces every lower bit b_k with b_k XOR b_{k+1} (XOR with the bit one position higher).

This is the standard binary-to-Gray conversion. The reverse — Gray to binary — uses a prefix XOR. Both are O(1) per index.

Visual Dry Run (binary representation trace)#

For n = 3, walk through all 8 indices.

i = 0 -> binary 000, i>>1 = 000 -> 000 XOR 000 = 000 (0)
i = 1 -> binary 001, i>>1 = 000 -> 001 XOR 000 = 001 (1)
i = 2 -> binary 010, i>>1 = 001 -> 010 XOR 001 = 011 (3)
i = 3 -> binary 011, i>>1 = 001 -> 011 XOR 001 = 010 (2)
i = 4 -> binary 100, i>>1 = 010 -> 100 XOR 010 = 110 (6)
i = 5 -> binary 101, i>>1 = 010 -> 101 XOR 010 = 111 (7)
i = 6 -> binary 110, i>>1 = 011 -> 110 XOR 011 = 101 (5)
i = 7 -> binary 111, i>>1 = 011 -> 111 XOR 011 = 100 (4)
 
Sequence: [0, 1, 3, 2, 6, 7, 5, 4]

Check adjacency: 001 -> 011 flips bit 1; 011 -> 010 flips bit 0; 010 -> 110 flips bit 2. Every step exactly one bit. The wrap from 100 -> 000 also flips one bit (bit 2).

Solution (Optimal)#

Python#

class Solution:
    def grayCode(self, n: int) -> list[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]

JavaScript#

var grayCode = function (n) {
  const result = [];
  const size = 1 << n;
  for (let i = 0; i < size; i++) {
    result.push(i ^ (i >> 1));
  }
  return result;
};

Complexity: Time O(2^n) to fill the output. Space O(2^n) for the result (or O(1) extra besides output).

Common Mistakes#

• Backtracking with a visited set. It works but takes O(n * 2^n) time and pages of code — interviewers will ask for the closed form.
• Confusing left and right shift. i << 1 doubles i — wrong. You need i >> 1 (the right shift, dropping the lowest bit).
• Forgetting the cyclic property. The last and first elements must also differ by one bit. The XOR formula guarantees this; ad-hoc constructions often miss it.
• Indexing past 2^n - 1. Use 1 << n for the loop bound; 1 << (n - 1) is half the sequence.
• Treating n = 0 as invalid. Per spec it should return [0] — handle the edge case.

Interview Tips#

• State the formula gray(i) = i XOR (i >> 1) as soon as you recognize the problem. Then prove the one-bit-difference property using the carry argument above.
• If asked to derive without recalling the formula: show the mirror construction — to build n-bit Gray, take (n-1)-bit Gray, append it reversed with a leading 1. That recursive construction is mathematically equivalent and demonstrates first-principles thinking.
• Mention the Gray-to-binary inverse: b_k = g_k XOR g_{k-1} XOR ... XOR g_0 (prefix XOR). Useful for follow-ups.
• Bring up real-world uses: rotary encoders, K-maps, Karnaugh minimization, anti-glitch counters.

Follow-up Questions#

1. Gray code starting from a given value start. XOR every result with start — translation preserves single-bit differences (LeetCode 1238 Circular Permutation in Binary Representation).
2. Convert Gray back to binary. binary[k] = gray[k] XOR binary[k+1], walking from MSB down — or use a single ^= loop.
3. n-bit reflected Gray code recursively. Demonstrates the mirror construction; useful for interviews focused on recursion.
4. Find the index i for a given Gray value g. Inverse of the formula — apply the prefix-XOR Gray-to-binary conversion.
5. What if you must enumerate Gray codes lexicographically? No longer the standard sequence — needs a different generator.

Key Takeaways#

• gray(i) = i XOR (i >> 1) is a one-line, O(1)-per-element generator — the canonical FAANG bit-manipulation trick.
• The formula works because adding 1 flips a trailing run, and XOR with the shifted version cancels all but the topmost flipped bit.
• The sequence wraps cyclically — last differs from first by one bit, for free.
• Backtracking solutions are accepted but signal weak bit-manipulation fluency. Reach for the formula.
• Gray codes have real-world hardware uses (encoders, K-maps) — bring this up to stand out.
• Master the inverse (Gray-to-binary prefix XOR) for follow-up questions.