Gray Code (LeetCode 89)
You get a number of bits, n. Build a list that holds every whole number from 0 to 2 ** n - 1 exactly once.
The list must follow three rules. It starts with 0. Each number and the number after it have binary forms that differ in exactly one place. The last number and the first number, 0, also differ in exactly one place.
Many lists follow these rules. Return any one of them.
Worked Examples
n = 2[0,1,3,2]00, 01, 11, 10. 00 to 01 changes the last place. 01 to 11 changes the first place. 11 to 10 changes the last place. 10 back to 00 changes the first place. The list [0,2,3,1] follows the rules too.n = 1[0,1]0 and 1 differ in their only place. The last number 1 is also one place away from the first number 0.⚖️Formal Constraints & Bounds
1 <= n <= 16Any list that follows the rules is accepted
Core Insight
Bit k of the code i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. Counting from i to i + 1 flips bits 0 to t, where t is the number of 1 bits at the low end of i. A pair of places inside that range flips both of its bits, so the pair keeps its answer. Only the pair at places t and t + 1 changes, so the code changes in exactly one bit, and the last code 100...0 is one bit from the first code 0.
Real-World Scenario & Production Applications
A rotary encoder reports the angle of a shaft as a binary number. With plain counting, some steps change several bits at once, such as 011 to 100. The sensors do not switch at exactly the same moment, so a reader can briefly see a wrong number such as 111. A Gray code changes one bit per step, so a reader sees either the old position or the new one.
Step-by-Step Execution Trace Table
Trace of n = 3: the loop runs for i from 0 to 7, and each row gives the code of position i.
i | i in binary | i >> 1 | i ^ (i >> 1) | code | place that changed from the row above |
|---|---|---|---|---|---|
| 0 | 000 | 000 | 000 | 0 | none |
| 1 | 001 | 000 | 001 | 1 | place 0 |
| 2 | 010 | 001 | 011 | 3 | place 1 |
| 3 | 011 | 001 | 010 | 2 | place 0 |
| 4 | 100 | 010 | 110 | 6 | place 2 |
| 5 | 101 | 010 | 111 | 7 | place 0 |
| 6 | 110 | 011 | 101 | 5 | place 1 |
| 7 | 111 | 011 | 100 | 4 | place 0 |
The function returns [0, 1, 3, 2, 6, 7, 5, 4]. Every row changes exactly one place. The last code 100 and the first code 000 also differ in exactly one place.
Another way to build the same list is to reflect it. Take the list for n - 1 bits, write it again in reverse order, and set the new top bit on every number of the copy. The two lists meet at the same number, and only the new top bit changes there. For n = 2, [0, 1] reflected is [1, 0], and with bit 1 set it is [3, 2], which gives [0, 1, 3, 2].
| 1 | codes = [] |
| 2 | for i in range(1 << n): |
| 3 | codes.append(i ^ (i >> 1)) |
| 4 | return codes |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A Gray code is a list of all 2 ** n numbers of n bits in which every number differs from the next one in exactly one bit. Plain counting does not do this: going from 01 to 10 changes two bits. The code i ^ (i >> 1) fixes this. The shift i >> 1 puts bit k + 1 of i at place k, so bit k of the code is 1 exactly when bits k and k + 1 of i differ.
Counting from i to i + 1 flips bits 0 to t, where t is the number of 1 bits at the low end of i. A pair of neighbouring places inside that range flips both bits, so the pair keeps its answer. Only the pair at places t and t + 1 changes, because bit t flips and bit t + 1 does not. That is exactly one bit of the code.
There is a second way to build the same list: reflect it. Take the list for n - 1 bits, write it again in reverse order, and set the new top bit on every number of the copy. The two lists meet at the same number, so only the new top bit changes there. The formula needs no list and no reversal, so it is the one to remember.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number to new places with shifts and masks. Here the number is combined with a shifted copy of itself by XOR, and a loop over all 2 ** n positions applies the same step to each one. The result is not one rearranged number but a whole list whose neighbours are one bit apart.
🔑 The Key Idea in the Code
Each code depends only on its own position i, so no code looks at the previous one. The one-bit rule between neighbours follows from the formula. The loop bound is 1 << n, because n is the number of bits and there are 2 ** n codes.
Using the forward code
n ^ (n >> 1): that turns a position into its code. Herenis the code and the answer is its position, which is the opposite direction. Forn = 6it returns 5, where 4 is right.Stopping before the last shift with
while n > 1: the highest bit ofnis never folded intoposition. Forn = 1it returns 0, where 1 is right.Adding with
+=instead of XOR with^=: the folded bits must cancel in pairs, and addition carries instead. Forn = 3it returns 4, where 2 is right.Carrying out the moves one at a time: the answer for
n = 109is 756249599, so a loop that applies each move runs about that many times and is too slow.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Differ in exactly one place" for each number and the next one, and "also from the last number back to the first": the order of all 2 ** n numbers matters, and the neighbours are only one bit apart. A rule that depends only on the position i points to a formula that turns i into its code.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After i rounds, codes holds the first i Gray codes, and each one differs from the code before it in exactly one bit. The code at position i is i ^ (i >> 1), and counting from i to i + 1 flips only the pair of places t and t + 1, where t is the number of 1 bits at the low end of i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A loop over
range(n):nis the number of bits, son = 3returns 3 codes where 8 are needed. The loop bound is1 << n.A loop that starts at position 1: the list does not start with 0, and
n = 2returns[1, 3, 2].|instead of^: two positions get the same code, andn = 2returns[0, 1, 3, 3].
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Gray Step. I give each position i the code i XOR i shifted right by one. The shift puts bit k plus one of i at place k, so bit k of the code is 1 exactly when two neighbouring bits of i differ. Counting from i to i plus one flips the low bits up to the first 0. Each pair of places inside that range flips both bits, so it keeps its answer. Only the pair at the top of the range changes, so the code changes in exactly one bit. The trap is the loop bound: the loop runs over 1 shifted left by n, which is two to the power n, not over n. For n equal to 3, the codes are 0, 1, 3, 2, 6, 7, 5, 4. The last code, 4, is one bit from 0. The loop runs two to the power n times with constant work in each round, so time is O of 2 to the n, which is the size of the output, and extra space is O of 1.
Complexity & Mathematical Proof
O(2^n)
Look at the loop. range(1 << n) runs 2 ** n rounds. Each round does one right shift, one XOR and one append, which is constant work for numbers of at most 16 bits. Time is therefore O(2^n). This is also the number of values in the output, so no algorithm can return the list faster.
O(1)
The code keeps the loop variable i and the list codes. codes is the output, with 2 ** n integers, and the output is not counted. The auxiliary space is O(1): i and one temporary value.
Derivation Progression
2^n
range(1 << n) gives every position from 0 to 2^n - 1 once.
3 = O(1)
One right shift, one XOR and one append.
Rounds times a constant amount of work.
Variable Definitions
The number of bits, 1 to 16
The position of a code in the list, from 0 to 2^n - 1
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the loop variable and one temporary value
O(2^n): the list of 2^n codes
Boundary Best / Worst Cases
: the loop always runs 2^n rounds, even for n = 1.
.
: 65536 rounds for n = 16.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The prompt asks for "a list of all 2 ** n numbers where each number differs from the next in exactly one bit". The order of the whole list matters, and the one-bit rule links only neighbours. A rule that depends only on the position i points to a formula: the code of position i is i ^ (i >> 1).
, so the list has at most numbers. The output itself has numbers, so time is and no algorithm is faster. Auxiliary space is , because each code is computed from its own position.
A loop over range(n) returns n codes instead of 2 ** n: n = 3 returns [0, 1, 3]. A loop that starts at position 1 leaves out 0: n = 2 returns [1, 3, 2]. i | (i >> 1) repeats a code: n = 2 returns [0, 1, 3, 3]. i << 1 instead of i >> 1 gives [0, 3, 6, 5] for n = 2.
Gray Code (LeetCode 89)
You get a number of bits, n. Build a list that holds every whole number from 0 to 2 ** n - 1 exactly once.
The list must follow three rules. It starts with 0. Each number and the number after it have binary forms that differ in exactly one place. The last number and the first number, 0, also differ in exactly one place.
Many lists follow these rules. Return any one of them.
Worked Examples
n = 2[0,1,3,2]00, 01, 11, 10. 00 to 01 changes the last place. 01 to 11 changes the first place. 11 to 10 changes the last place. 10 back to 00 changes the first place. The list [0,2,3,1] follows the rules too.n = 1[0,1]0 and 1 differ in their only place. The last number 1 is also one place away from the first number 0.⚖️Formal Constraints & Bounds
1 <= n <= 16Any list that follows the rules is accepted
Core Insight
Bit k of the code i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. Counting from i to i + 1 flips bits 0 to t, where t is the number of 1 bits at the low end of i. A pair of places inside that range flips both of its bits, so the pair keeps its answer. Only the pair at places t and t + 1 changes, so the code changes in exactly one bit, and the last code 100...0 is one bit from the first code 0.
Real-World Scenario & Production Applications
A rotary encoder reports the angle of a shaft as a binary number. With plain counting, some steps change several bits at once, such as 011 to 100. The sensors do not switch at exactly the same moment, so a reader can briefly see a wrong number such as 111. A Gray code changes one bit per step, so a reader sees either the old position or the new one.
Step-by-Step Execution Trace Table
Trace of n = 3: the loop runs for i from 0 to 7, and each row gives the code of position i.
i | i in binary | i >> 1 | i ^ (i >> 1) | code | place that changed from the row above |
|---|---|---|---|---|---|
| 0 | 000 | 000 | 000 | 0 | none |
| 1 | 001 | 000 | 001 | 1 | place 0 |
| 2 | 010 | 001 | 011 | 3 | place 1 |
| 3 | 011 | 001 | 010 | 2 | place 0 |
| 4 | 100 | 010 | 110 | 6 | place 2 |
| 5 | 101 | 010 | 111 | 7 | place 0 |
| 6 | 110 | 011 | 101 | 5 | place 1 |
| 7 | 111 | 011 | 100 | 4 | place 0 |
The function returns [0, 1, 3, 2, 6, 7, 5, 4]. Every row changes exactly one place. The last code 100 and the first code 000 also differ in exactly one place.
Another way to build the same list is to reflect it. Take the list for n - 1 bits, write it again in reverse order, and set the new top bit on every number of the copy. The two lists meet at the same number, and only the new top bit changes there. For n = 2, [0, 1] reflected is [1, 0], and with bit 1 set it is [3, 2], which gives [0, 1, 3, 2].
| 1 | codes = [] |
| 2 | for i in range(1 << n): |
| 3 | codes.append(i ^ (i >> 1)) |
| 4 | return codes |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A Gray code is a list of all 2 ** n numbers of n bits in which every number differs from the next one in exactly one bit. Plain counting does not do this: going from 01 to 10 changes two bits. The code i ^ (i >> 1) fixes this. The shift i >> 1 puts bit k + 1 of i at place k, so bit k of the code is 1 exactly when bits k and k + 1 of i differ.
Counting from i to i + 1 flips bits 0 to t, where t is the number of 1 bits at the low end of i. A pair of neighbouring places inside that range flips both bits, so the pair keeps its answer. Only the pair at places t and t + 1 changes, because bit t flips and bit t + 1 does not. That is exactly one bit of the code.
There is a second way to build the same list: reflect it. Take the list for n - 1 bits, write it again in reverse order, and set the new top bit on every number of the copy. The two lists meet at the same number, so only the new top bit changes there. The formula needs no list and no reversal, so it is the one to remember.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number to new places with shifts and masks. Here the number is combined with a shifted copy of itself by XOR, and a loop over all 2 ** n positions applies the same step to each one. The result is not one rearranged number but a whole list whose neighbours are one bit apart.
🔑 The Key Idea in the Code
Each code depends only on its own position i, so no code looks at the previous one. The one-bit rule between neighbours follows from the formula. The loop bound is 1 << n, because n is the number of bits and there are 2 ** n codes.
Using the forward code
n ^ (n >> 1): that turns a position into its code. Herenis the code and the answer is its position, which is the opposite direction. Forn = 6it returns 5, where 4 is right.Stopping before the last shift with
while n > 1: the highest bit ofnis never folded intoposition. Forn = 1it returns 0, where 1 is right.Adding with
+=instead of XOR with^=: the folded bits must cancel in pairs, and addition carries instead. Forn = 3it returns 4, where 2 is right.Carrying out the moves one at a time: the answer for
n = 109is 756249599, so a loop that applies each move runs about that many times and is too slow.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Differ in exactly one place" for each number and the next one, and "also from the last number back to the first": the order of all 2 ** n numbers matters, and the neighbours are only one bit apart. A rule that depends only on the position i points to a formula that turns i into its code.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After i rounds, codes holds the first i Gray codes, and each one differs from the code before it in exactly one bit. The code at position i is i ^ (i >> 1), and counting from i to i + 1 flips only the pair of places t and t + 1, where t is the number of 1 bits at the low end of i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A loop over
range(n):nis the number of bits, son = 3returns 3 codes where 8 are needed. The loop bound is1 << n.A loop that starts at position 1: the list does not start with 0, and
n = 2returns[1, 3, 2].|instead of^: two positions get the same code, andn = 2returns[0, 1, 3, 3].
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Gray Step. I give each position i the code i XOR i shifted right by one. The shift puts bit k plus one of i at place k, so bit k of the code is 1 exactly when two neighbouring bits of i differ. Counting from i to i plus one flips the low bits up to the first 0. Each pair of places inside that range flips both bits, so it keeps its answer. Only the pair at the top of the range changes, so the code changes in exactly one bit. The trap is the loop bound: the loop runs over 1 shifted left by n, which is two to the power n, not over n. For n equal to 3, the codes are 0, 1, 3, 2, 6, 7, 5, 4. The last code, 4, is one bit from 0. The loop runs two to the power n times with constant work in each round, so time is O of 2 to the n, which is the size of the output, and extra space is O of 1.
Complexity & Mathematical Proof
O(2^n)
Look at the loop. range(1 << n) runs 2 ** n rounds. Each round does one right shift, one XOR and one append, which is constant work for numbers of at most 16 bits. Time is therefore O(2^n). This is also the number of values in the output, so no algorithm can return the list faster.
O(1)
The code keeps the loop variable i and the list codes. codes is the output, with 2 ** n integers, and the output is not counted. The auxiliary space is O(1): i and one temporary value.
Derivation Progression
2^n
range(1 << n) gives every position from 0 to 2^n - 1 once.
3 = O(1)
One right shift, one XOR and one append.
Rounds times a constant amount of work.
Variable Definitions
The number of bits, 1 to 16
The position of a code in the list, from 0 to 2^n - 1
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the loop variable and one temporary value
O(2^n): the list of 2^n codes
Boundary Best / Worst Cases
: the loop always runs 2^n rounds, even for n = 1.
.
: 65536 rounds for n = 16.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The prompt asks for "a list of all 2 ** n numbers where each number differs from the next in exactly one bit". The order of the whole list matters, and the one-bit rule links only neighbours. A rule that depends only on the position i points to a formula: the code of position i is i ^ (i >> 1).
, so the list has at most numbers. The output itself has numbers, so time is and no algorithm is faster. Auxiliary space is , because each code is computed from its own position.
A loop over range(n) returns n codes instead of 2 ** n: n = 3 returns [0, 1, 3]. A loop that starts at position 1 leaves out 0: n = 2 returns [1, 3, 2]. i | (i >> 1) repeats a code: n = 2 returns [0, 1, 3, 3]. i << 1 instead of i >> 1 gives [0, 3, 6, 5] for n = 2.