Loading…

mediumBit ManipulationLC #89Sometimes asked

Gray Code Generation

Q: How do you solve Gray Code Generation using the Reflect and Prefix (Constructive Baseline) approach?

When to use it: Lead with this if you don't recall the formula — it derives Gray code from its definition. Build the sequence by repeatedly mirroring and tagging a new high bit. **Start small.** The 0-bit Gray code is `[0]`. To go from `k` bits to `k+1` bits, take the current list and its reverse. **Reflect.** Write the current list as-is (these implicitly have a leading 0 in the new bit position), then write it again in reverse order with the new high bit set: add `1 << k` to each reflected element. **Why one bit changes at the seam.** Within the first half, adjacency is inherited from the smaller valid code. Within the second half, it's the same code reversed, so adjacency still holds. At the boundary between the two halves, the lower bits are identical (it's a mirror) and only the freshly added high bit differs — exactly one bit. The wrap-around from last to first flips only that high bit too. **Repeat n times.** After n doublings the list holds all 2ⁿ codes. This is literally the definition of the *reflected* Gray code, which is why the formula approach produces the same ordering. Time complexity: O(2ⁿ). Space complexity: O(2ⁿ).

Q: How do you solve Gray Code Generation using the Direct Formula — i ^ (i >> 1) (Optimal) approach?

When to use it: The crisp answer. Phrase it as 'the i-th Gray code is just i XOR (i shifted right by one)'. Map each counter value straight to its Gray code with one XOR. **The formula.** The i-th reflected Gray code is `i ^ (i >> 1)`. You iterate i over the normal binary counter 0, 1, 2, …, 2ⁿ - 1 and convert each value on the fly. **Why XOR with the shift gives one-bit steps.** In Gray code, bit `j` of `gray(i)` equals `bit_j(i) XOR bit_{j+1}(i)` — each Gray bit is the XOR of two adjacent binary bits, which is exactly what `i ^ (i >> 1)` computes. When the counter goes from `i` to `i + 1`, binary addition flips a run of low bits: the lowest 0 becomes 1 and the 1s below it become 0. After the XOR-with-shift, all those cascading flips cancel out in pairs, leaving precisely one changed bit between `gray(i)` and `gray(i + 1)`. **Why it starts at 0 and wraps cleanly.** `gray(0) = 0 ^ 0 = 0`, satisfying the leading-0 requirement. The reflected code is cyclic, so `gray(2ⁿ - 1)` and `gray(0)` also differ in a single bit — the formula reproduces the same reflected ordering as the constructive build, so it inherits that wrap-around property. **Store the code, not the index.** The classic slip is appending `i` instead of `i ^ (i >> 1)`. You loop over the index but emit the converted value. Time complexity: O(2ⁿ). Space complexity: O(2ⁿ).

LCPractice

Bit Manipulation · 9 of 20 · 9 min

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

Every integer is in the inclusive range [0, 2ⁿ - 1],
The first integer is 0,
An integer appears no more than once,
The binary representations of every pair of adjacent integers differ by exactly one bit, and
The binary representations of the first and last integers also differ by exactly one bit.

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

In plain English

Produce all 2ⁿ patterns of n bits, ordered so each consecutive pair (and the wrap-around pair) differs in a single bit. The list must start at 0. The standard reflected Gray code satisfies all of this, and the formula i ^ (i >> 1) generates exactly that ordering.

Examples

Example 1

Input: n = 2
Output: [0, 1, 3, 2]
Note: Binary 00, 01, 11, 10. Each adjacent pair flips one bit, and 10 → 00 (last to first) also flips one.

Example 2

Input: n = 1
Output: [0, 1]
Note: 00→1 differs by one bit; wrap 1→0 also one bit.

Example 3

Input: n = 3
Output: [0, 1, 3, 2, 6, 7, 5, 4]
Note: Binary 000,001,011,010,110,111,101,100 — every step is a single-bit flip.

Constraints

1 ≤ n ≤ 16
The output has exactly 2ⁿ integers
Multiple valid sequences exist; any correct one is accepted

Clarifying questions4First question: Does the sequence have to start at 0?Explore questions

Q1.Does the sequence have to start at 0?
Yes, the spec fixes the first element at 0. The formula naturally starts there since 0 ^ 0 = 0.
Q2.Must the first and last also differ by one bit?
Yes — it's a cyclic code. The reflected Gray code guarantees this wrap-around property automatically.
Q3.Is any valid ordering accepted, or a specific one?
Any valid Gray code is accepted. I'll return the canonical reflected one via i ^ (i >> 1).
Q4.How large can n get?
Up to 16, so 2ⁿ is at most 65536 entries — generating the full list is fine.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

An n-bit Gray code is a sequence of all 2ⁿ numbers where consecutive entries differ in exactly one bit. The cleanest construction is the formula `gray(i) = i ^ (i >> 1)` for i from 0 to 2ⁿ - 1. XORing i with its own right-shift cancels all but the single-bit transitions, so each step flips exactly one bit. It runs in O(2ⁿ) time, one O(1) formula per element.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the i ^ (i >> 1) identity (or can derive the reflect construction) and understand why each step flips exactly one bit.

Where candidates slip

Storing the loop index i instead of the converted code i ^ (i >> 1), or building only 2ⁿ - 1 entries by an off-by-one in the loop bound.

How to stand out

Show the O(1)-per-element formula, explain why XOR with the shift isolates single-bit transitions, and mention the equivalent reflect-and-prefix recursion.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Reflect and Prefix (Constructive Baseline)	`O(2ⁿ)`	`O(2ⁿ)`	Lead with this if you don't recall the formula — it derives Gray code from its definition.	Read
2	Direct Formula — i ^ (i >> 1) (Optimal)Optimal	`O(2ⁿ)`	`O(2ⁿ)`	The crisp answer. Phrase it as 'the i-th Gray code is just i XOR (i shifted right by one)'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewBuild n-bit Gray codeRemember the formula?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Reflect and Prefix (Constructive Baseline)

TimeO(2ⁿ)SpaceO(2ⁿ)

Lead with this if you don't recall the formula — it derives Gray code from its definition.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you have a valid (n-1)-bit Gray code. How could you extend it to n bits while keeping the one-bit-change property?

2Hint 2Explore hint

Take the (n-1)-bit list, then append its reverse. The original half keeps a leading 0; the reflected half gets a leading 1.

3Hint 3Explore hint

At the mirror seam the two halves share the same lower bits, so only the new high bit changes — one bit. Start from [0] and repeat n times.

A · Core idea

Build the sequence by repeatedly mirroring and tagging a new high bit.

Start small. The 0-bit Gray code is [0]. To go from k bits to k+1 bits, take the current list and its reverse.

Reflect. Write the current list as-is (these implicitly have a leading 0 in the new bit position), then write it again in reverse order with the new high bit set: add 1 << k to each reflected element.

Why one bit changes at the seam. Within the first half, adjacency is inherited from the smaller valid code. Within the second half, it's the same code reversed, so adjacency still holds. At the boundary between the two halves, the lower bits are identical (it's a mirror) and only the freshly added high bit differs — exactly one bit. The wrap-around from last to first flips only that high bit too.

Repeat n times. After n doublings the list holds all 2ⁿ codes. This is literally the definition of the reflected Gray code, which is why the formula approach produces the same ordering.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

have

1-bit code

[0]

end ↓

[1]

Current pointerResolved stateNot processed

Final result[0, 1, 3, 2]

C · Code with teaching comments

Reference implementation previewpublic List<Integer> grayCode(int n) { List<Integer> result = new ArrayList<>(); result.add(0); for (int k = 0; k < n; k++) { int highBit = 1 << k;Explore the full code

solution.javaJava

Reflect and Prefix (Constructive Baseline) — reference

3 teaching notes

1
public List<Integer> grayCode(int n) {
2
    List<Integer> result = new ArrayList<>();
3
    result.add(0);
4
    for (int k = 0; k < n; k++) {
5
        // The new most-significant bit introduced this round.
6
        int highBit = 1 << k;
7
        // Walk the existing list backward — that reversal is the 'reflect'.
8
        for (int i = result.size() - 1; i >= 0; i--) {
9
            result.add(result.get(i) | highBit); // reflect + set new bit
10
        }
11
    }
12
    return result;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(2ⁿ) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proof

Reflection is what guarantees the single-bit seam: a mirrored copy shares lower bits at the join, so adding one new high bit is the only change. Recognizing 'mirror then prefix' as the generator demystifies the formula.

ComplexityO(2ⁿ) time, O(2ⁿ) space — Each doubling step processes the current list once; the list sizes are 1, 2, 4, …, 2ⁿ, summing to about 2ⁿ⁺¹. So total work and output are O(2ⁿ).

E · Edge cases and pitfalls3Forgetting to reverse the reflected half — neighbors then differ by more than one bit.Explore edge cases

Pitfalls

Forgetting to reverse the reflected half — neighbors then differ by more than one bit.
Setting the wrong bit (using k+1 or n instead of k) when OR-ing the high bit.
Starting from an empty list instead of [0], breaking the required leading 0.

03.2

Approach 2 of 2 · Optimal

Direct Formula — i ^ (i >> 1) (Optimal)

TimeO(2ⁿ)SpaceO(2ⁿ)

The crisp answer. Phrase it as 'the i-th Gray code is just i XOR (i shifted right by one)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Is there a direct map from a plain counter value i to its Gray code, with no list-building?

2Hint 2Explore hint

Try gray(i) = i ^ (i >> 1). Compute it for i = 0,1,2,3 and compare bits with the reflected sequence.

3Hint 3Explore hint

Loop i from 0 to 2ⁿ - 1 and append i ^ (i >> 1). The output size 2ⁿ is unavoidable; the per-element work is O(1).

A · Core idea

Map each counter value straight to its Gray code with one XOR.

The formula. The i-th reflected Gray code is i ^ (i >> 1). You iterate i over the normal binary counter 0, 1, 2, …, 2ⁿ - 1 and convert each value on the fly.

Why XOR with the shift gives one-bit steps. In Gray code, bit j of gray(i) equals bit_j(i) XOR bit_{j+1}(i) — each Gray bit is the XOR of two adjacent binary bits, which is exactly what i ^ (i >> 1) computes. When the counter goes from i to i + 1, binary addition flips a run of low bits: the lowest 0 becomes 1 and the 1s below it become 0. After the XOR-with-shift, all those cascading flips cancel out in pairs, leaving precisely one changed bit between gray(i) and gray(i + 1).

Why it starts at 0 and wraps cleanly. gray(0) = 0 ^ 0 = 0, satisfying the leading-0 requirement. The reflected code is cyclic, so gray(2ⁿ - 1) and gray(0) also differ in a single bit — the formula reproduces the same reflected ordering as the constructive build, so it inherits that wrap-around property.

Store the code, not the index. The classic slip is appending i instead of i ^ (i >> 1). You loop over the index but emit the converted value.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

i = 0,1

0→0, 1→1

[0]

i ↓

[1]

Current pointerResolved stateNot processed

Final result[0, 1, 3, 2]

C · Code with teaching comments

solution.javaJava

Direct Formula — i ^ (i >> 1) (Optimal) — optimal

2 teaching notes

1
public List<Integer> grayCode(int n) {
2
    List<Integer> result = new ArrayList<>();
3
    // Exactly 2ⁿ codes are required — the loop bound.
4
    int total = 1 << n; // 2^n
5
    for (int i = 0; i < total; i++) {
6
        // Convert the counter value i to its Gray code; store the code, never i itself.
7
        result.add(i ^ (i >> 1));
8
    }
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(2ⁿ) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proof

i ^ (i >> 1) works because each Gray bit is the parity of two neighboring binary bits. The carry cascade of incrementing a counter flips a contiguous block of bits, and XOR-ing with the shifted copy collapses that block to a single net change — that's the whole reason consecutive Gray codes are one bit apart.

ComplexityO(2ⁿ) time, O(2ⁿ) space — The loop runs 2ⁿ times, each iteration doing one shift and one XOR in O(1). Producing 2ⁿ outputs is the lower bound, so the formula is optimal; space is O(2ⁿ) for the result list.

E · Edge cases and pitfalls7n = 1 — i = 0,1 → [0, 1]; wrap 1→0 flips one bit.Explore edge cases

Edge cases handled

n = 1i = 0,1 → [0, 1]; wrap 1→0 flips one bit.
n = 01 << 0 = 1, loop runs once → [0]; a single code, trivially valid.
n = 1665536 entries; each still one shift + XOR, no overflow within int range.
last vs firstgray(2ⁿ-1) differs from gray(0)=0 by one bit — the reflected code is cyclic.

Pitfalls

Appending i instead of i ^ (i >> 1) — outputs plain binary, not Gray code.
Using i >> 1 with a signed shift on a negative i — not an issue here since i ≥ 0.
Off-by-one loop bound producing 2ⁿ - 1 or 2ⁿ + 1 entries.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<Integer> grayCode(int n) { List<Integer> result = new ArrayList<>(); int total = 1 << n; // 2^n for (int i = 0; i < total; i++) { result.add(i ^ (i >> 1));Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Emitting the index instead of the Gray code

Iterating i and appending i gives plain binary counting, where i=1 (01) to i=2 (10) flips two bits — not a Gray code.

Explore the code comparison

Don't write this

return [i for i in range(1 << n)]  # plain binary, not Gray

Write this instead

return [i ^ (i >> 1) for i in range(1 << n)]

Reflection without reversal

In the constructive build, appending the half forward instead of reversed breaks the single-bit seam, so adjacent codes can differ in multiple bits.

Explore the code comparison

Don't write this

for (int i = 0; i < result.size(); i++) { // forward = wrong
    result.add(result.get(i) | highBit);
}

Write this instead

for (int i = result.size() - 1; i >= 0; i--) { // reversed = reflect
    result.add(result.get(i) | highBit);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary-to-Gray formula: g = i ^ (i >> 1)

Code pattern to memorize

for i in 0 .. (1<<n) - 1:
    result.append(i ^ (i >> 1))

Rules to remember

1gray(i) = i ^ (i >> 1) converts the i-th integer into the i-th Gray code directly.
2The sequence has exactly 2ⁿ entries and starts at 0 — that start is part of the spec.
3Consecutive codes differ in one bit; so do the first and last (it's a cyclic / reflected code).
4The recursive 'reflect' build is equivalent: mirror the list and prefix the new high bit with 1.
5Don't confuse the index i with the code value — you iterate i, but you store i ^ (i >> 1).

Use this pattern when

Generating sequences where neighbors change in a single bit (hardware encoders, K-maps)
Minimizing switching when stepping through all bit patterns
Any 'list all 2ⁿ states, one-bit change between steps' construction
Mapping a counter to a glitch-free encoder value

Choose another pattern when

Need all subsets in any order → plain 0..2ⁿ-1 bitmask enumeration, no Gray ordering
Need permutations, not bit patterns → backtracking, not Gray code
Need to decode Gray back to binary → cumulative XOR, a different formula
n is huge → 2ⁿ output is infeasible regardless of method

Interview takeaway

The Gray code formula `i ^ (i >> 1)` is the one-liner to memorize: it turns a normal counter into a one-bit-change-per-step sequence. The reflect-and-prefix recursion is the same idea built bottom-up.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGray code construction: the formula i ^ (i >> 1) maps a counter to a one-bit-change sequence, and the reflect-and-prefix recursion builds the same reflected code. The bit-parity idea recurs in encoding and subset-enumeration problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Circular Permutation in Binary Representation
Coming soon
Generate Gray code then XOR every entry with the desired start value to rotate the cycle.
Subsets
Coming soon
If order doesn't matter, enumerate 0..2ⁿ-1 directly; Gray ordering is only for single-bit transitions.
Single Number II
Coming soon
Another bit-parity construction — track bit counts mod 3 with XOR-style state.
Gray to Binary Decoding
Coming soon
Reverse the formula: binary = cumulative XOR of Gray bits from the most significant down.

Same pattern

←

Bitwise AND of Numbers Range

Continue · Next problem

Power of Two

mediumBit ManipulationLC #89Sometimes asked

Gray Code Generation

LCPractice

Bit Manipulation · 9 of 20 · 9 min

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

Every integer is in the inclusive range [0, 2ⁿ - 1],
The first integer is 0,
An integer appears no more than once,
The binary representations of every pair of adjacent integers differ by exactly one bit, and
The binary representations of the first and last integers also differ by exactly one bit.

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

In plain English

Examples

Example 1

Input: n = 2
Output: [0, 1, 3, 2]
Note: Binary 00, 01, 11, 10. Each adjacent pair flips one bit, and 10 → 00 (last to first) also flips one.

Example 2

Input: n = 1
Output: [0, 1]
Note: 00→1 differs by one bit; wrap 1→0 also one bit.

Example 3

Input: n = 3
Output: [0, 1, 3, 2, 6, 7, 5, 4]
Note: Binary 000,001,011,010,110,111,101,100 — every step is a single-bit flip.

Constraints

1 ≤ n ≤ 16
The output has exactly 2ⁿ integers
Multiple valid sequences exist; any correct one is accepted

Clarifying questions4First question: Does the sequence have to start at 0?Explore questions

Q1.Does the sequence have to start at 0?
Yes, the spec fixes the first element at 0. The formula naturally starts there since 0 ^ 0 = 0.
Q2.Must the first and last also differ by one bit?
Yes — it's a cyclic code. The reflected Gray code guarantees this wrap-around property automatically.
Q3.Is any valid ordering accepted, or a specific one?
Any valid Gray code is accepted. I'll return the canonical reflected one via i ^ (i >> 1).
Q4.How large can n get?
Up to 16, so 2ⁿ is at most 65536 entries — generating the full list is fine.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the i ^ (i >> 1) identity (or can derive the reflect construction) and understand why each step flips exactly one bit.

Where candidates slip

Storing the loop index i instead of the converted code i ^ (i >> 1), or building only 2ⁿ - 1 entries by an off-by-one in the loop bound.

How to stand out

Show the O(1)-per-element formula, explain why XOR with the shift isolates single-bit transitions, and mention the equivalent reflect-and-prefix recursion.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Reflect and Prefix (Constructive Baseline)	`O(2ⁿ)`	`O(2ⁿ)`	Lead with this if you don't recall the formula — it derives Gray code from its definition.	Read
2	Direct Formula — i ^ (i >> 1) (Optimal)Optimal	`O(2ⁿ)`	`O(2ⁿ)`	The crisp answer. Phrase it as 'the i-th Gray code is just i XOR (i shifted right by one)'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Reflect and Prefix (Constructive Baseline)

TimeO(2ⁿ)SpaceO(2ⁿ)

Lead with this if you don't recall the formula — it derives Gray code from its definition.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you have a valid (n-1)-bit Gray code. How could you extend it to n bits while keeping the one-bit-change property?

2Hint 2Explore hint

Take the (n-1)-bit list, then append its reverse. The original half keeps a leading 0; the reflected half gets a leading 1.

3Hint 3Explore hint

At the mirror seam the two halves share the same lower bits, so only the new high bit changes — one bit. Start from [0] and repeat n times.

A · Core idea

Build the sequence by repeatedly mirroring and tagging a new high bit.

Start small. The 0-bit Gray code is [0]. To go from k bits to k+1 bits, take the current list and its reverse.

Repeat n times. After n doublings the list holds all 2ⁿ codes. This is literally the definition of the reflected Gray code, which is why the formula approach produces the same ordering.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

have

1-bit code

[0]

end ↓

[1]

Current pointerResolved stateNot processed

Final result[0, 1, 3, 2]

C · Code with teaching comments

solution.javaJava

Reflect and Prefix (Constructive Baseline) — reference

3 teaching notes

1
public List<Integer> grayCode(int n) {
2
    List<Integer> result = new ArrayList<>();
3
    result.add(0);
4
    for (int k = 0; k < n; k++) {
5
        // The new most-significant bit introduced this round.
6
        int highBit = 1 << k;
7
        // Walk the existing list backward — that reversal is the 'reflect'.
8
        for (int i = result.size() - 1; i >= 0; i--) {
9
            result.add(result.get(i) | highBit); // reflect + set new bit
10
        }
11
    }
12
    return result;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(2ⁿ) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Forgetting to reverse the reflected half — neighbors then differ by more than one bit.Explore edge cases

Pitfalls

Forgetting to reverse the reflected half — neighbors then differ by more than one bit.
Setting the wrong bit (using k+1 or n instead of k) when OR-ing the high bit.
Starting from an empty list instead of [0], breaking the required leading 0.

03.2

Approach 2 of 2 · Optimal

Direct Formula — i ^ (i >> 1) (Optimal)

TimeO(2ⁿ)SpaceO(2ⁿ)

The crisp answer. Phrase it as 'the i-th Gray code is just i XOR (i shifted right by one)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Is there a direct map from a plain counter value i to its Gray code, with no list-building?

2Hint 2Explore hint

Try gray(i) = i ^ (i >> 1). Compute it for i = 0,1,2,3 and compare bits with the reflected sequence.

3Hint 3Explore hint

Loop i from 0 to 2ⁿ - 1 and append i ^ (i >> 1). The output size 2ⁿ is unavoidable; the per-element work is O(1).

A · Core idea

Map each counter value straight to its Gray code with one XOR.

The formula. The i-th reflected Gray code is i ^ (i >> 1). You iterate i over the normal binary counter 0, 1, 2, …, 2ⁿ - 1 and convert each value on the fly.

Store the code, not the index. The classic slip is appending i instead of i ^ (i >> 1). You loop over the index but emit the converted value.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2

Array state

i = 0,1

0→0, 1→1

[0]

i ↓

[1]

Current pointerResolved stateNot processed

Final result[0, 1, 3, 2]

C · Code with teaching comments

solution.javaJava

Direct Formula — i ^ (i >> 1) (Optimal) — optimal

2 teaching notes

1
public List<Integer> grayCode(int n) {
2
    List<Integer> result = new ArrayList<>();
3
    // Exactly 2ⁿ codes are required — the loop bound.
4
    int total = 1 << n; // 2^n
5
    for (int i = 0; i < total; i++) {
6
        // Convert the counter value i to its Gray code; store the code, never i itself.
7
        result.add(i ^ (i >> 1));
8
    }
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(2ⁿ) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7n = 1 — i = 0,1 → [0, 1]; wrap 1→0 flips one bit.Explore edge cases

Edge cases handled

n = 1i = 0,1 → [0, 1]; wrap 1→0 flips one bit.
n = 01 << 0 = 1, loop runs once → [0]; a single code, trivially valid.
n = 1665536 entries; each still one shift + XOR, no overflow within int range.
last vs firstgray(2ⁿ-1) differs from gray(0)=0 by one bit — the reflected code is cyclic.

Pitfalls

Appending i instead of i ^ (i >> 1) — outputs plain binary, not Gray code.
Using i >> 1 with a signed shift on a negative i — not an issue here since i ≥ 0.
Off-by-one loop bound producing 2ⁿ - 1 or 2ⁿ + 1 entries.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Emitting the index instead of the Gray code

Iterating i and appending i gives plain binary counting, where i=1 (01) to i=2 (10) flips two bits — not a Gray code.

Explore the code comparison

Don't write this

return [i for i in range(1 << n)]  # plain binary, not Gray

Write this instead

return [i ^ (i >> 1) for i in range(1 << n)]

Reflection without reversal

In the constructive build, appending the half forward instead of reversed breaks the single-bit seam, so adjacent codes can differ in multiple bits.

Explore the code comparison

Don't write this

for (int i = 0; i < result.size(); i++) { // forward = wrong
    result.add(result.get(i) | highBit);
}

Write this instead

for (int i = result.size() - 1; i >= 0; i--) { // reversed = reflect
    result.add(result.get(i) | highBit);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary-to-Gray formula: g = i ^ (i >> 1)

Code pattern to memorize

for i in 0 .. (1<<n) - 1:
    result.append(i ^ (i >> 1))

Rules to remember

1gray(i) = i ^ (i >> 1) converts the i-th integer into the i-th Gray code directly.
2The sequence has exactly 2ⁿ entries and starts at 0 — that start is part of the spec.
3Consecutive codes differ in one bit; so do the first and last (it's a cyclic / reflected code).
4The recursive 'reflect' build is equivalent: mirror the list and prefix the new high bit with 1.
5Don't confuse the index i with the code value — you iterate i, but you store i ^ (i >> 1).

Use this pattern when

Generating sequences where neighbors change in a single bit (hardware encoders, K-maps)
Minimizing switching when stepping through all bit patterns
Any 'list all 2ⁿ states, one-bit change between steps' construction
Mapping a counter to a glitch-free encoder value

Choose another pattern when

Need all subsets in any order → plain 0..2ⁿ-1 bitmask enumeration, no Gray ordering
Need permutations, not bit patterns → backtracking, not Gray code
Need to decode Gray back to binary → cumulative XOR, a different formula
n is huge → 2ⁿ output is infeasible regardless of method

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Circular Permutation in Binary Representation
Coming soon
Generate Gray code then XOR every entry with the desired start value to rotate the cycle.
Subsets
Coming soon
If order doesn't matter, enumerate 0..2ⁿ-1 directly; Gray ordering is only for single-bit transitions.
Single Number II
Coming soon
Another bit-parity construction — track bit counts mod 3 with XOR-style state.
Gray to Binary Decoding
Coming soon
Reverse the formula: binary = cumulative XOR of Gray bits from the most significant down.

Same pattern

←

Bitwise AND of Numbers Range

Continue · Next problem

Power of Two