Gray Code

Gray code looks like a permutation problem, but the useful signal is more specific: enumerate every n-bit state so that each move flips exactly one bit, including the move back to the start.

The clean approach is to derive the sequence with reflection and submit the equivalent direct formula:

def grayCode(n: int) -> list[int]:
    total = 1 << n
    return [i ^ (i >> 1) for i in range(total)]

The code is short. The interview value is being able to explain why this transform satisfies the entire cyclic contract.

The contract: a cyclic one-bit sequence

For an input n, return exactly 2^n integers such that:

• Every value is between 0 and 2^n - 1.
• The first value is 0.
• No value appears more than once.
• Every adjacent pair differs in exactly one binary bit.
• The last and first values also differ in exactly one bit.

That final condition makes the sequence cyclic. You are constructing a loop, not merely a path.

For n = 2, one valid sequence is:

[0, 1, 3, 2]

Using two-bit representations:

00 -> 01 -> 11 -> 10 -> 00

Each transition changes one bit position.

Be precise about “one bit.” It means Hamming distance one, not numeric difference one. The transition 01 -> 10 has numeric difference 1, but both bit positions changed:

01
10

Core invariant: every value appears exactly once, every neighboring pair has Hamming distance one, and the sequence closes with the same property.

Any valid ordering is accepted. The sample ordering is not special.

Recognize the structure before coding

The visible task is “generate a sequence.” The real task is:

Order every n-bit mask so that moving to the next mask changes exactly one bit, including the wraparound from the last mask to the first.

Ordinary binary counting reaches every value but fails at carry boundaries:

01 -> 10

Both bits change. At a larger boundary:

0111 -> 1000

four bits change at once.

A backtracking solution could start at 0, try flipping each bit, avoid visited values, and search for a complete cycle. That models the constraints, but it ignores the stronger fact: the bit structure gives us a deterministic construction.

There is also an unavoidable output-size bound. The result contains 2^n integers, so materializing it already requires Ω(2^n) output work. The target is therefore not polynomial time in n; it is linear in the number of values the contract requires.

The right move is to remove search, not to pretend the output is small.

Derive the reflected construction

Start with the zero-bit sequence:

[0]

To add one bit:

1. Keep the current sequence as the first half.
2. Traverse the current sequence backward.
3. Set the new bit in each reflected value.
4. Append the reflected values.

For the first bit:

[0]

Reflect and set bit 0:

[0, 1]

For the next bit, reflect [0, 1]:

[1, 0]

Set bit 1:

[3, 2]

Append:

[0, 1, 3, 2]

In binary:

00 -> 01 -> 11 -> 10

The new boundary is:

01 -> 11

Only the newly added bit changes.

For n = 3, repeat the same operation:

[0, 1, 3, 2, 6, 7, 5, 4]

or:

000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100

Suppose the old sequence is:

a0, a1, ..., ak

The next sequence is:

0a0, 0a1, ..., 0ak, 1ak, ..., 1a1, 1a0

The old transitions remain valid in the first half. Reversing the sequence preserves adjacency in the second half. At the junction:

0ak -> 1ak

only the new leading bit changes.

The endpoints also close correctly. The first value is 0a0; the last is 1a0. They differ only in the new bit, assuming the old sequence already closed correctly.

This gives the induction invariant:

• The sequence contains every value for the current bit width exactly once.
• Every internal adjacent pair differs in one bit.
• The first and last values differ in one bit.

Each reflection step preserves all three properties.

Reflection implementation

This version mirrors the derivation:

def grayCode_reflected(n: int) -> list[int]:
    result = [0]

    for bit in range(n):
        size = len(result)

        for index in range(size - 1, -1, -1):
            result.append(result[index] | (1 << bit))

    return result

Capture size before appending. That boundary represents the old sequence. If the loop used the changing length, it would start processing newly created values during the same reflection step.

The expression:

value | (1 << bit)

sets the new bit while preserving all lower bits. Every old value has that bit clear at this stage, so the appended half is a distinct copy with the new bit enabled.

Turn the construction into a direct formula

Reflection explains how to build the sequence, but we can map each required index directly:

g(i) = i XOR (i >> 1)

For each binary index i:

1. Shift i right by one position.
2. XOR the original value with the shifted value.

For n = 3:

The output is:

[0, 1, 3, 2, 6, 7, 5, 4]

This formula is not a separate trick. It is the closed form of the reflected ordering.

If the bits of i are:

b[n-1] b[n-2] ... b[1] b[0]

then the Gray-code bits are:

b[n-1],
b[n-1] XOR b[n-2],
...,
b[1] XOR b[0]

The highest output bit copies the highest input bit. Each lower output bit compares neighboring input bits.

My implementation decision is straightforward:

Use reflection to discover and explain the sequence. Use the direct formula to submit it because each output position maps directly to one index.

Prove the formula correct

The submitted implementation is the formula, so its proof should address the formula directly. Reflection gives the intuition; the following argument connects the code to the one-bit invariant.

Count and range

The loop visits:

range(1 << n)

That contains exactly 2^n indices, from 0 through 2^n - 1.

For every such i, both i and i >> 1 fit within n bits. Their XOR therefore also fits within n bits, so every result lies in:

[0, 2^n - 1]

The sequence starts at zero

For i = 0:

g(0) = 0 ^ (0 >> 1) = 0

The first value is correct.

No duplicates

The transform is reversible.

Let b be the original binary number and g its Gray code. The highest bit is unchanged:

b[n - 1] = g[n - 1]

Each lower binary bit can then be recovered from the bit above it:

b[k] = b[k + 1] XOR g[k]

For example, decode Gray code 101:

b[2] = 1
b[1] = 1 XOR 0 = 1
b[0] = 1 XOR 1 = 0

The original binary value is 110.

Because each Gray value maps back to exactly one binary index, two different indices cannot produce the same result. The transform is injective, so the 2^n generated values are distinct.

Adjacent values differ by one bit

This is the step that should not be hand-waved.

Take an index i, and let t be the position of its lowest zero bit. In other words:

• Bits 0 through t - 1 of i are all 1.
• Bit t is 0.
• Incrementing i changes those trailing 1s to 0s and changes bit t to 1.

So the binary increment has this shape:

... 0 111...111
       t bits

becoming:

... 1 000...000
       t bits

Now consider the Gray bits. For input bits b[j], the Gray bit at position j is:

g[j] = b[j] XOR b[j + 1]

All positions below t remain unchanged in the Gray representation:

• Inside the trailing run of 1s, neighboring bits are equal.
• Inside the new run of 0s, neighboring bits are also equal.
• At the boundary below bit t, the relevant XOR remains the same.

At position t, however, b[t] changes from 0 to 1 while b[t + 1] does not change. Therefore:

g(i)[t] != g(i + 1)[t]

Every other Gray bit stays unchanged. Thus:

g(i) XOR g(i + 1)

has exactly one set bit, so adjacent outputs differ in exactly one bit.

The formula has now earned the same adjacency guarantee that reflection made visible.

The sequence closes

The final index is:

i = 2^n - 1

Its bits are all 1:

111...111

After shifting right:

011...111

XORing them leaves only the highest bit:

g(2^n - 1) = 100...000 = 1 << (n - 1)

The first value is 0, so the final and first values differ only in that highest bit. The cyclic edge is valid.

Dry-run the Python solution

The submission is:

def grayCode(n: int) -> list[int]:
    total = 1 << n
    return [i ^ (i >> 1) for i in range(total)]

For n = 2, total is 4:

Therefore:

[0, 1, 3, 2]

The list comprehension performs one constant-time bitwise calculation per required output. There is no hidden search.

A common debugging error is to test adjacency using subtraction:

abs(a - b) == 1

That checks numeric distance, not bit distance. Use XOR instead:

def differs_by_one_bit(a: int, b: int) -> bool:
    difference = a ^ b
    return difference != 0 and (difference & (difference - 1)) == 0

The expression x & (x - 1) clears the lowest set bit. It equals zero exactly when x contains one set bit.

For a compact full-contract check:

def valid_gray_code(sequence: list[int], n: int) -> bool:
    total = 1 << n

    if len(sequence) != total:
        return False
    if sequence[0] != 0:
        return False
    if any(value < 0 or value >= total for value in sequence):
        return False
    if len(set(sequence)) != total:
        return False

    pairs = zip(sequence, sequence[1:] + sequence[:1])
    return all(differs_by_one_bit(a, b) for a, b in pairs)

The final pair in pairs is the wraparound pair, so the validator checks the cyclic condition rather than only the linear path.

Complexity and edge cases

The direct formula generates one result for each of the 2^n required values.

• Time: O(2^n)
• Returned output space: O(2^n)
• Auxiliary space beyond the returned list: O(1)

The exponential output is forced by the contract. There is no way to materialize 2^n integers in less than output-sized space.

Important cases:

• n = 1 produces [0, 1]. The wraparound 1 -> 0 changes one bit.
• n = 2 exposes the complete reflection pattern: [0, 1, 3, 2].
• n = 0 produces [0] and is useful as the mathematical base case, although it is outside the supplied constraint 1 <= n <= 16.
• The maximum input requires a large result, but the algorithm performs only the required generation work.

When debugging, check the contract in order:

1. Is the length 2^n?
2. Is the first value 0?
3. Are all values in range?
4. Are all values unique?
5. Does every consecutive pair differ in one bit?
6. Does the last value differ from the first in one bit?

The reusable recognition rule

When a problem asks you to enumerate every bitmask exactly once, with one-bit transitions between neighboring states and a one-bit wraparound, look for a reflected construction or a binary-to-Gray transform before reaching for backtracking.

The durable skill is not memorizing:

[0, 1, 3, 2]

It is recognizing the invariant, deriving the reflection, and then knowing why:

i ^ (i >> 1)

preserves the entire cyclic contract.