What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

One-Bit Steps (Gray Code)

Built on

Bit TricksMake the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The problem

Gray Code (LC 89)(opens leetcode.com)

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.

Example 1

Input:n = 2

Output:[0,1,3,2]

In binary the list is 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.

Gray Step

n bits ➔ for each position i: code = i ^ (i >> 1) ➔ 2 ** n codes, neighbours differ in one bit

Spot it when: You must list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit, or find the position of a pattern in that order.

Gray Step

Python

1	def gray_code(n: int) -> list[int]:
2	"""Gray Code: the code at position i is i ^ (i >> 1), so neighbouring codes differ in exactly one bit.
3	Time: O(2^n) \| Space: O(1) auxiliary, the output is not counted
4	"""
5	# codes: the Gray code of every position from 0 to 2^n - 1, in position order
6	codes = []
7
8	# 1. Visit Every Position Once:
9	# An n-bit code has 2^n values, and 1 << n is 2^n, so the loop covers every position from 0 to 2^n - 1.
10	for i in range(1 << n):
11	# 2. Compare Each Bit With The Bit Above It:
12	# i >> 1 puts bit k + 1 of i at place k, so i ^ (i >> 1) has a 1 at place k exactly when bits k and k + 1 of i differ.
13	codes.append(i ^ (i >> 1))
14	return codes

Invariant: 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 for position i is i ^ (i >> 1): 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. For every pair of places k and k + 1 inside that range, both bits flip, so the pair still differs or still agrees as before. Only the pair at places t and t + 1 changes, because bit t flips and bit t + 1 does not, so each code differs from the code before it in exactly one bit. The trap is the loop bound: write range(1 << n), not range(n), because n is the number of bits and there are 2 ** n codes.

See it run

Gray Code for n = 4, step by step

i -code -codes held 0

The rows are i, i >> 1 and the code i ^ (i >> 1). Each column is one bit position, with the highest position on the left.

flipped a bit of the code that differs from the same place in the previous code

Start: n = 4 bits, so the loop runs for i from 0 to 15. The list codes is empty.

i >> 1

code

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Looping range(n) instead of range(1 << n)
Mistake
```
for i in range(n):
```
Fix
```
for i in range(1 << n):
```
What happens: n is the number of bits, not the number of codes. An n-bit code has 2 ** n values, and 1 << n is 2 ** n. range(n) runs only n rounds, so codes stops after the first n positions. For n = 3 it holds 3 codes where 8 are needed.
Example: Gray Code (LC 89): n = 3
Mistake: returns [0, 1, 3]Fix: returns [0, 1, 3, 2, 6, 7, 5, 4]
Gotcha 2: Starting the loop at position 1 with range(1, 1 << n)
Mistake
```
for i in range(1, 1 << n):
```
Fix
```
for i in range(1 << n):
```
What happens: The sequence must start at 0 and contain every value from 0 to 2 ** n - 1. Position 0 has the code 0 ^ (0 >> 1), which is 0. Starting at position 1 leaves that code out, so codes has one value too few and does not begin with 0.
Example: Gray Code (LC 89): n = 2
Mistake: returns [1, 3, 2]Fix: returns [0, 1, 3, 2]
Gotcha 3: Using | instead of ^ to combine i with i >> 1
Mistake
```
codes.append(i | (i >> 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: ^ gives 1 only where the two bits differ, and that is what the code needs. | gives 1 where at least one of the two bits is 1, so two different positions can get the same code. For n = 2, positions 2 and 3 both give 3, and the value 2 is never produced.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 1, 3, 3]Fix: returns [0, 1, 3, 2]
Gotcha 4: Shifting left with i << 1 instead of right with i >> 1
Mistake
```
codes.append(i ^ (i << 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: i << 1 puts bit k of i at place k + 1, so every bit is compared with the bit below it, and the top bit moves to place n. A code can then be 2 ** n or larger. For n = 2, position 1 gives 3, which differs from the code 0 in two bits, and position 2 gives 6, which is outside 0 to 3.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 3, 6, 5]Fix: returns [0, 1, 3, 2]

Not this one if…

You need every subset in any order, as in Subsets (LC 78), so counting mask from 0 to 2 ** n - 1 is enough and no neighbour rule applies. See Bitmask Subsets
You count the 1 bits of every number from 0 to n, as in Counting Bits (LC 338); no bit pattern has to be built. See Kernighan's Bit Trick
The bits of one number must move to other places, as in Reverse Bits (LC 190), instead of being combined with a shifted copy of the same number. See Bit Tricks

Deep Dive

Why neighbouring codes differ in one bit

Bit k of i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. So the code records, for every pair of neighbouring places in i, whether the two bits are different.

Counting from i to i + 1 flips bits 0 to t of i, where t is the number of 1 bits at the low end of i. Inside that range, a pair of places flips both bits, so the pair keeps its answer. The pair at places t and t + 1 flips only bit t, so only that code bit changes.

Example with n = 4: the codes are 0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, which is 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000. The board above walks through all 16. The bit that changes at position i is the lowest 1 bit of i: places 0, 1, 0, 2, 0, 1, 0, 3 and so on.

I checked this for every n from 0 to 10: the codes are exactly the numbers 0 to 2 ** n - 1, and every neighbouring pair differs in one bit.

Why the loop is range(1 << n) and why XOR is needed

n is the number of bits, and an n-bit code has 2 ** n values. 1 << n is 2 ** n, so range(1 << n) visits every position once. range(n) for n = 4 gives only the codes 0, 1, 3, 2.

The code must be a one-to-one map from positions to values. XOR keeps all information of i, so no two positions share a code. OR does not. For n = 2, the positions 0, 1, 2, 3 give 0, 1, 3, 3 with OR. The value 2 is never produced.

The sequence also closes: the last code and the first code differ in one bit. For n = 4, 8 and 0 differ only in place 3.

The cost, and two other ways to see the same list

The loop runs 2 ** n times and each round does one shift and one XOR. The time is O(2^n). The output has 2 ** n numbers, and the extra space is O(1) when the output is not counted.

Reflection: the codes for n bits are the codes for n - 1 bits, followed by the same list in reverse order with bit n - 1 set. For n = 1 the list is 0, 1. For n = 2 it is 0, 1, 3, 2. I checked that this equals i ^ (i >> 1) for n from 1 to 8.

Inverse: to find the position of a code, XOR the code with itself shifted right by 1, then by 2, and so on, until it is 0. For the code 14 this gives position 11. The code at position 11 for n = 4 is 14.

Gray Code (LC 89) accepts any valid sequence that starts at 0, so this list is one correct answer.

60-Second Pitch

"The code for position i is i ^ (i >> 1). The shift puts each bit next to the bit below it, and XOR marks where the two differ. Counting from i to i + 1 flips the low bits up to the first 0. Every pair of places inside that range flips both bits and keeps its answer, so exactly one code bit changes. I loop over range(1 << n) because n is the number of bits and there are 2 ** n codes. That is O(2^n) time and O(1) extra space. If the question asks for the position of a code, I XOR the code with its right shifts to invert it."

Common Questions

What is the time and space complexity of gray_code?: O(2^n) time, because there are 2 ** n codes and each takes constant work. The extra space is O(1) when the output is not counted.
Why does i ^ (i >> 1) change only one bit from one position to the next?: Bit k of the code says whether bits k and k + 1 of i differ. Going to i + 1 flips bits 0 to t. Pairs inside that range flip both bits and keep their answer. Only the pair at places t and t + 1 changes.
How do you get the position of a given Gray code?: XOR the code with itself shifted right by 1, 2, 3 and so on, until the shifted value is 0. For the code 14 this gives 11. I checked that this inverts the formula for every position when n is below 10.
Is this the only valid answer for Gray Code (LC 89)?: No. Other orders also have neighbours that differ in one bit. This list is the reflected one: the list for n - 1 bits, then the same list reversed with bit n - 1 set. It starts at 0, as the problem requires.
How does this build on Bit Tricks?: Bit Tricks moves bits with shifts and masks. This card adds one move: XOR a number with itself shifted right by 1, so each code bit compares two neighbouring bits of i.

SWE Reasoning

Spot it

The statement asks for all 2 ** n bit patterns in an order where neighbours differ in exactly one bit.
The statement asks for the position of a pattern in that order, or the pattern at a position.
A hardware or puzzle story needs a change of one bit at a time: a rotary encoder, a lock with switches, a walk over the corners of a cube.
A first idea is backtracking over all patterns. That works, but a formula gives the list in O(2^n) with no search.

The invariant, step by step

Start with codes = []. After 0 rounds it holds 0 codes, which is correct.
In round i, i >> 1 puts bit k + 1 of i at place k.
i ^ (i >> 1) is 1 at place k exactly when bits k and k + 1 of i differ.
The step from i to i + 1 flips bits 0 to t of i. Every pair inside that range keeps its answer, and only the pair at places t and t + 1 changes.
So the new code differs from the previous code in exactly one bit.
After 2 ** n rounds, codes holds every value from 0 to 2 ** n - 1 once, in Gray order.

Traps

range(n) instead of range(1 << n). n is the number of bits. For n = 3 the list has 3 codes where 8 are needed.
range(1, 1 << n). The list leaves out the code for position 0. For n = 2 it is [1, 3, 2] and does not start at 0.
| instead of ^. OR gives 1 where either bit is 1, so two positions can share a code. For n = 2 the value 2 is never produced.
i ^ (i << 1). A left shift moves bits up, so the code compares bit k with bit k - 1. The list grows past 2 ** n - 1 for most i, and the values are not in the range 0 to 2 ** n - 1.

Practice

Canonical LeetCode:Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

One-Bit Steps (Gray Code)

Built on

Bit TricksMake the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The problem

Gray Code (LC 89)(opens leetcode.com)

You get a number of bits, n. Build a list that holds every whole number from 0 to 2 ** n - 1 exactly once.

Many lists follow these rules. Return any one of them.

Example 1

Input:n = 2

Output:[0,1,3,2]

Gray Step

n bits ➔ for each position i: code = i ^ (i >> 1) ➔ 2 ** n codes, neighbours differ in one bit

Spot it when: You must list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit, or find the position of a pattern in that order.

Gray Step

Python

1	def gray_code(n: int) -> list[int]:
2	"""Gray Code: the code at position i is i ^ (i >> 1), so neighbouring codes differ in exactly one bit.
3	Time: O(2^n) \| Space: O(1) auxiliary, the output is not counted
4	"""
5	# codes: the Gray code of every position from 0 to 2^n - 1, in position order
6	codes = []
7
8	# 1. Visit Every Position Once:
9	# An n-bit code has 2^n values, and 1 << n is 2^n, so the loop covers every position from 0 to 2^n - 1.
10	for i in range(1 << n):
11	# 2. Compare Each Bit With The Bit Above It:
12	# i >> 1 puts bit k + 1 of i at place k, so i ^ (i >> 1) has a 1 at place k exactly when bits k and k + 1 of i differ.
13	codes.append(i ^ (i >> 1))
14	return codes

Invariant: After i rounds, codes holds the first i Gray codes, and each one differs from the code before it in exactly one bit.

See it run

Gray Code for n = 4, step by step

i -code -codes held 0

The rows are i, i >> 1 and the code i ^ (i >> 1). Each column is one bit position, with the highest position on the left.

flipped a bit of the code that differs from the same place in the previous code

Start: n = 4 bits, so the loop runs for i from 0 to 15. The list codes is empty.

i >> 1

code

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Looping range(n) instead of range(1 << n)
Mistake
```
for i in range(n):
```
Fix
```
for i in range(1 << n):
```
What happens: n is the number of bits, not the number of codes. An n-bit code has 2 ** n values, and 1 << n is 2 ** n. range(n) runs only n rounds, so codes stops after the first n positions. For n = 3 it holds 3 codes where 8 are needed.
Example: Gray Code (LC 89): n = 3
Mistake: returns [0, 1, 3]Fix: returns [0, 1, 3, 2, 6, 7, 5, 4]
Gotcha 2: Starting the loop at position 1 with range(1, 1 << n)
Mistake
```
for i in range(1, 1 << n):
```
Fix
```
for i in range(1 << n):
```
What happens: The sequence must start at 0 and contain every value from 0 to 2 ** n - 1. Position 0 has the code 0 ^ (0 >> 1), which is 0. Starting at position 1 leaves that code out, so codes has one value too few and does not begin with 0.
Example: Gray Code (LC 89): n = 2
Mistake: returns [1, 3, 2]Fix: returns [0, 1, 3, 2]
Gotcha 3: Using | instead of ^ to combine i with i >> 1
Mistake
```
codes.append(i | (i >> 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: ^ gives 1 only where the two bits differ, and that is what the code needs. | gives 1 where at least one of the two bits is 1, so two different positions can get the same code. For n = 2, positions 2 and 3 both give 3, and the value 2 is never produced.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 1, 3, 3]Fix: returns [0, 1, 3, 2]
Gotcha 4: Shifting left with i << 1 instead of right with i >> 1
Mistake
```
codes.append(i ^ (i << 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: i << 1 puts bit k of i at place k + 1, so every bit is compared with the bit below it, and the top bit moves to place n. A code can then be 2 ** n or larger. For n = 2, position 1 gives 3, which differs from the code 0 in two bits, and position 2 gives 6, which is outside 0 to 3.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 3, 6, 5]Fix: returns [0, 1, 3, 2]

Not this one if…

You need every subset in any order, as in Subsets (LC 78), so counting mask from 0 to 2 ** n - 1 is enough and no neighbour rule applies. See Bitmask Subsets
You count the 1 bits of every number from 0 to n, as in Counting Bits (LC 338); no bit pattern has to be built. See Kernighan's Bit Trick
The bits of one number must move to other places, as in Reverse Bits (LC 190), instead of being combined with a shifted copy of the same number. See Bit Tricks

Deep Dive

Why neighbouring codes differ in one bit

Bit k of i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. So the code records, for every pair of neighbouring places in i, whether the two bits are different.

I checked this for every n from 0 to 10: the codes are exactly the numbers 0 to 2 ** n - 1, and every neighbouring pair differs in one bit.

Why the loop is range(1 << n) and why XOR is needed

n is the number of bits, and an n-bit code has 2 ** n values. 1 << n is 2 ** n, so range(1 << n) visits every position once. range(n) for n = 4 gives only the codes 0, 1, 3, 2.

The sequence also closes: the last code and the first code differ in one bit. For n = 4, 8 and 0 differ only in place 3.

The cost, and two other ways to see the same list

The loop runs 2 ** n times and each round does one shift and one XOR. The time is O(2^n). The output has 2 ** n numbers, and the extra space is O(1) when the output is not counted.

Gray Code (LC 89) accepts any valid sequence that starts at 0, so this list is one correct answer.

60-Second Pitch

Common Questions

What is the time and space complexity of gray_code?: O(2^n) time, because there are 2 ** n codes and each takes constant work. The extra space is O(1) when the output is not counted.
Why does i ^ (i >> 1) change only one bit from one position to the next?: Bit k of the code says whether bits k and k + 1 of i differ. Going to i + 1 flips bits 0 to t. Pairs inside that range flip both bits and keep their answer. Only the pair at places t and t + 1 changes.
How do you get the position of a given Gray code?: XOR the code with itself shifted right by 1, 2, 3 and so on, until the shifted value is 0. For the code 14 this gives 11. I checked that this inverts the formula for every position when n is below 10.
Is this the only valid answer for Gray Code (LC 89)?: No. Other orders also have neighbours that differ in one bit. This list is the reflected one: the list for n - 1 bits, then the same list reversed with bit n - 1 set. It starts at 0, as the problem requires.
How does this build on Bit Tricks?: Bit Tricks moves bits with shifts and masks. This card adds one move: XOR a number with itself shifted right by 1, so each code bit compares two neighbouring bits of i.

SWE Reasoning

Spot it

The statement asks for all 2 ** n bit patterns in an order where neighbours differ in exactly one bit.
The statement asks for the position of a pattern in that order, or the pattern at a position.
A hardware or puzzle story needs a change of one bit at a time: a rotary encoder, a lock with switches, a walk over the corners of a cube.
A first idea is backtracking over all patterns. That works, but a formula gives the list in O(2^n) with no search.

The invariant, step by step

Start with codes = []. After 0 rounds it holds 0 codes, which is correct.
In round i, i >> 1 puts bit k + 1 of i at place k.
i ^ (i >> 1) is 1 at place k exactly when bits k and k + 1 of i differ.
The step from i to i + 1 flips bits 0 to t of i. Every pair inside that range keeps its answer, and only the pair at places t and t + 1 changes.
So the new code differs from the previous code in exactly one bit.
After 2 ** n rounds, codes holds every value from 0 to 2 ** n - 1 once, in Gray order.

Traps

range(n) instead of range(1 << n). n is the number of bits. For n = 3 the list has 3 codes where 8 are needed.
range(1, 1 << n). The list leaves out the code for position 0. For n = 2 it is [1, 3, 2] and does not start at 0.
| instead of ^. OR gives 1 where either bit is 1, so two positions can share a code. For n = 2 the value 2 is never produced.
i ^ (i << 1). A left shift moves bits up, so the code compares bit k with bit k - 1. The list grows past 2 ** n - 1 for most i, and the values are not in the range 0 to 2 ** n - 1.

Practice

Canonical LeetCode:Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

One-Bit Steps (Gray Code)

Built on

Bit TricksMake the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The problem

Gray Code (LC 89)(opens leetcode.com)

You get a number of bits, n. Build a list that holds every whole number from 0 to 2 ** n - 1 exactly once.

Many lists follow these rules. Return any one of them.

Example 1

Input:n = 2

Output:[0,1,3,2]

Gray Step

n bits ➔ for each position i: code = i ^ (i >> 1) ➔ 2 ** n codes, neighbours differ in one bit

Spot it when: You must list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit, or find the position of a pattern in that order.

Gray Step

Python

1	def gray_code(n: int) -> list[int]:
2	"""Gray Code: the code at position i is i ^ (i >> 1), so neighbouring codes differ in exactly one bit.
3	Time: O(2^n) \| Space: O(1) auxiliary, the output is not counted
4	"""
5	# codes: the Gray code of every position from 0 to 2^n - 1, in position order
6	codes = []
7
8	# 1. Visit Every Position Once:
9	# An n-bit code has 2^n values, and 1 << n is 2^n, so the loop covers every position from 0 to 2^n - 1.
10	for i in range(1 << n):
11	# 2. Compare Each Bit With The Bit Above It:
12	# i >> 1 puts bit k + 1 of i at place k, so i ^ (i >> 1) has a 1 at place k exactly when bits k and k + 1 of i differ.
13	codes.append(i ^ (i >> 1))
14	return codes

Invariant: After i rounds, codes holds the first i Gray codes, and each one differs from the code before it in exactly one bit.

See it run

Gray Code for n = 4, step by step

i -code -codes held 0

The rows are i, i >> 1 and the code i ^ (i >> 1). Each column is one bit position, with the highest position on the left.

flipped a bit of the code that differs from the same place in the previous code

Start: n = 4 bits, so the loop runs for i from 0 to 15. The list codes is empty.

i >> 1

code

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Looping range(n) instead of range(1 << n)
Mistake
```
for i in range(n):
```
Fix
```
for i in range(1 << n):
```
What happens: n is the number of bits, not the number of codes. An n-bit code has 2 ** n values, and 1 << n is 2 ** n. range(n) runs only n rounds, so codes stops after the first n positions. For n = 3 it holds 3 codes where 8 are needed.
Example: Gray Code (LC 89): n = 3
Mistake: returns [0, 1, 3]Fix: returns [0, 1, 3, 2, 6, 7, 5, 4]
Gotcha 2: Starting the loop at position 1 with range(1, 1 << n)
Mistake
```
for i in range(1, 1 << n):
```
Fix
```
for i in range(1 << n):
```
What happens: The sequence must start at 0 and contain every value from 0 to 2 ** n - 1. Position 0 has the code 0 ^ (0 >> 1), which is 0. Starting at position 1 leaves that code out, so codes has one value too few and does not begin with 0.
Example: Gray Code (LC 89): n = 2
Mistake: returns [1, 3, 2]Fix: returns [0, 1, 3, 2]
Gotcha 3: Using | instead of ^ to combine i with i >> 1
Mistake
```
codes.append(i | (i >> 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: ^ gives 1 only where the two bits differ, and that is what the code needs. | gives 1 where at least one of the two bits is 1, so two different positions can get the same code. For n = 2, positions 2 and 3 both give 3, and the value 2 is never produced.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 1, 3, 3]Fix: returns [0, 1, 3, 2]
Gotcha 4: Shifting left with i << 1 instead of right with i >> 1
Mistake
```
codes.append(i ^ (i << 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: i << 1 puts bit k of i at place k + 1, so every bit is compared with the bit below it, and the top bit moves to place n. A code can then be 2 ** n or larger. For n = 2, position 1 gives 3, which differs from the code 0 in two bits, and position 2 gives 6, which is outside 0 to 3.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 3, 6, 5]Fix: returns [0, 1, 3, 2]

Not this one if…

You need every subset in any order, as in Subsets (LC 78), so counting mask from 0 to 2 ** n - 1 is enough and no neighbour rule applies. See Bitmask Subsets
You count the 1 bits of every number from 0 to n, as in Counting Bits (LC 338); no bit pattern has to be built. See Kernighan's Bit Trick
The bits of one number must move to other places, as in Reverse Bits (LC 190), instead of being combined with a shifted copy of the same number. See Bit Tricks

Deep Dive

Why neighbouring codes differ in one bit

Bit k of i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. So the code records, for every pair of neighbouring places in i, whether the two bits are different.

I checked this for every n from 0 to 10: the codes are exactly the numbers 0 to 2 ** n - 1, and every neighbouring pair differs in one bit.

Why the loop is range(1 << n) and why XOR is needed

n is the number of bits, and an n-bit code has 2 ** n values. 1 << n is 2 ** n, so range(1 << n) visits every position once. range(n) for n = 4 gives only the codes 0, 1, 3, 2.

The sequence also closes: the last code and the first code differ in one bit. For n = 4, 8 and 0 differ only in place 3.

The cost, and two other ways to see the same list

The loop runs 2 ** n times and each round does one shift and one XOR. The time is O(2^n). The output has 2 ** n numbers, and the extra space is O(1) when the output is not counted.

Gray Code (LC 89) accepts any valid sequence that starts at 0, so this list is one correct answer.

60-Second Pitch

Common Questions

What is the time and space complexity of gray_code?: O(2^n) time, because there are 2 ** n codes and each takes constant work. The extra space is O(1) when the output is not counted.
Why does i ^ (i >> 1) change only one bit from one position to the next?: Bit k of the code says whether bits k and k + 1 of i differ. Going to i + 1 flips bits 0 to t. Pairs inside that range flip both bits and keep their answer. Only the pair at places t and t + 1 changes.
How do you get the position of a given Gray code?: XOR the code with itself shifted right by 1, 2, 3 and so on, until the shifted value is 0. For the code 14 this gives 11. I checked that this inverts the formula for every position when n is below 10.
Is this the only valid answer for Gray Code (LC 89)?: No. Other orders also have neighbours that differ in one bit. This list is the reflected one: the list for n - 1 bits, then the same list reversed with bit n - 1 set. It starts at 0, as the problem requires.
How does this build on Bit Tricks?: Bit Tricks moves bits with shifts and masks. This card adds one move: XOR a number with itself shifted right by 1, so each code bit compares two neighbouring bits of i.

SWE Reasoning

Spot it

The statement asks for all 2 ** n bit patterns in an order where neighbours differ in exactly one bit.
The statement asks for the position of a pattern in that order, or the pattern at a position.
A hardware or puzzle story needs a change of one bit at a time: a rotary encoder, a lock with switches, a walk over the corners of a cube.
A first idea is backtracking over all patterns. That works, but a formula gives the list in O(2^n) with no search.

The invariant, step by step

Start with codes = []. After 0 rounds it holds 0 codes, which is correct.
In round i, i >> 1 puts bit k + 1 of i at place k.
i ^ (i >> 1) is 1 at place k exactly when bits k and k + 1 of i differ.
The step from i to i + 1 flips bits 0 to t of i. Every pair inside that range keeps its answer, and only the pair at places t and t + 1 changes.
So the new code differs from the previous code in exactly one bit.
After 2 ** n rounds, codes holds every value from 0 to 2 ** n - 1 once, in Gray order.

Traps

range(n) instead of range(1 << n). n is the number of bits. For n = 3 the list has 3 codes where 8 are needed.
range(1, 1 << n). The list leaves out the code for position 0. For n = 2 it is [1, 3, 2] and does not start at 0.
| instead of ^. OR gives 1 where either bit is 1, so two positions can share a code. For n = 2 the value 2 is never produced.
i ^ (i << 1). A left shift moves bits up, so the code compares bit k with bit k - 1. The list grows past 2 ** n - 1 for most i, and the values are not in the range 0 to 2 ** n - 1.

Practice

Canonical LeetCode:Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

One-Bit Steps (Gray Code)

Built on

Bit TricksMake the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The problem

Gray Code (LC 89)(opens leetcode.com)

You get a number of bits, n. Build a list that holds every whole number from 0 to 2 ** n - 1 exactly once.

Many lists follow these rules. Return any one of them.

Example 1

Input:n = 2

Output:[0,1,3,2]

Gray Step

n bits ➔ for each position i: code = i ^ (i >> 1) ➔ 2 ** n codes, neighbours differ in one bit

Spot it when: You must list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit, or find the position of a pattern in that order.

Gray Step

Python

1	def gray_code(n: int) -> list[int]:
2	"""Gray Code: the code at position i is i ^ (i >> 1), so neighbouring codes differ in exactly one bit.
3	Time: O(2^n) \| Space: O(1) auxiliary, the output is not counted
4	"""
5	# codes: the Gray code of every position from 0 to 2^n - 1, in position order
6	codes = []
7
8	# 1. Visit Every Position Once:
9	# An n-bit code has 2^n values, and 1 << n is 2^n, so the loop covers every position from 0 to 2^n - 1.
10	for i in range(1 << n):
11	# 2. Compare Each Bit With The Bit Above It:
12	# i >> 1 puts bit k + 1 of i at place k, so i ^ (i >> 1) has a 1 at place k exactly when bits k and k + 1 of i differ.
13	codes.append(i ^ (i >> 1))
14	return codes

Invariant: After i rounds, codes holds the first i Gray codes, and each one differs from the code before it in exactly one bit.

See it run

Gray Code for n = 4, step by step

i -code -codes held 0

The rows are i, i >> 1 and the code i ^ (i >> 1). Each column is one bit position, with the highest position on the left.

flipped a bit of the code that differs from the same place in the previous code

Start: n = 4 bits, so the loop runs for i from 0 to 15. The list codes is empty.

i >> 1

code

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Looping range(n) instead of range(1 << n)
Mistake
```
for i in range(n):
```
Fix
```
for i in range(1 << n):
```
What happens: n is the number of bits, not the number of codes. An n-bit code has 2 ** n values, and 1 << n is 2 ** n. range(n) runs only n rounds, so codes stops after the first n positions. For n = 3 it holds 3 codes where 8 are needed.
Example: Gray Code (LC 89): n = 3
Mistake: returns [0, 1, 3]Fix: returns [0, 1, 3, 2, 6, 7, 5, 4]
Gotcha 2: Starting the loop at position 1 with range(1, 1 << n)
Mistake
```
for i in range(1, 1 << n):
```
Fix
```
for i in range(1 << n):
```
What happens: The sequence must start at 0 and contain every value from 0 to 2 ** n - 1. Position 0 has the code 0 ^ (0 >> 1), which is 0. Starting at position 1 leaves that code out, so codes has one value too few and does not begin with 0.
Example: Gray Code (LC 89): n = 2
Mistake: returns [1, 3, 2]Fix: returns [0, 1, 3, 2]
Gotcha 3: Using | instead of ^ to combine i with i >> 1
Mistake
```
codes.append(i | (i >> 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: ^ gives 1 only where the two bits differ, and that is what the code needs. | gives 1 where at least one of the two bits is 1, so two different positions can get the same code. For n = 2, positions 2 and 3 both give 3, and the value 2 is never produced.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 1, 3, 3]Fix: returns [0, 1, 3, 2]
Gotcha 4: Shifting left with i << 1 instead of right with i >> 1
Mistake
```
codes.append(i ^ (i << 1))
```
Fix
```
codes.append(i ^ (i >> 1))
```
What happens: i << 1 puts bit k of i at place k + 1, so every bit is compared with the bit below it, and the top bit moves to place n. A code can then be 2 ** n or larger. For n = 2, position 1 gives 3, which differs from the code 0 in two bits, and position 2 gives 6, which is outside 0 to 3.
Example: Gray Code (LC 89): n = 2
Mistake: returns [0, 3, 6, 5]Fix: returns [0, 1, 3, 2]

Not this one if…

You need every subset in any order, as in Subsets (LC 78), so counting mask from 0 to 2 ** n - 1 is enough and no neighbour rule applies. See Bitmask Subsets
You count the 1 bits of every number from 0 to n, as in Counting Bits (LC 338); no bit pattern has to be built. See Kernighan's Bit Trick
The bits of one number must move to other places, as in Reverse Bits (LC 190), instead of being combined with a shifted copy of the same number. See Bit Tricks

Deep Dive

Why neighbouring codes differ in one bit

Bit k of i ^ (i >> 1) is 1 exactly when bits k and k + 1 of i differ. So the code records, for every pair of neighbouring places in i, whether the two bits are different.

I checked this for every n from 0 to 10: the codes are exactly the numbers 0 to 2 ** n - 1, and every neighbouring pair differs in one bit.

Why the loop is range(1 << n) and why XOR is needed

n is the number of bits, and an n-bit code has 2 ** n values. 1 << n is 2 ** n, so range(1 << n) visits every position once. range(n) for n = 4 gives only the codes 0, 1, 3, 2.

The sequence also closes: the last code and the first code differ in one bit. For n = 4, 8 and 0 differ only in place 3.

The cost, and two other ways to see the same list

The loop runs 2 ** n times and each round does one shift and one XOR. The time is O(2^n). The output has 2 ** n numbers, and the extra space is O(1) when the output is not counted.

Gray Code (LC 89) accepts any valid sequence that starts at 0, so this list is one correct answer.

60-Second Pitch

Common Questions

What is the time and space complexity of gray_code?: O(2^n) time, because there are 2 ** n codes and each takes constant work. The extra space is O(1) when the output is not counted.
Why does i ^ (i >> 1) change only one bit from one position to the next?: Bit k of the code says whether bits k and k + 1 of i differ. Going to i + 1 flips bits 0 to t. Pairs inside that range flip both bits and keep their answer. Only the pair at places t and t + 1 changes.
How do you get the position of a given Gray code?: XOR the code with itself shifted right by 1, 2, 3 and so on, until the shifted value is 0. For the code 14 this gives 11. I checked that this inverts the formula for every position when n is below 10.
Is this the only valid answer for Gray Code (LC 89)?: No. Other orders also have neighbours that differ in one bit. This list is the reflected one: the list for n - 1 bits, then the same list reversed with bit n - 1 set. It starts at 0, as the problem requires.
How does this build on Bit Tricks?: Bit Tricks moves bits with shifts and masks. This card adds one move: XOR a number with itself shifted right by 1, so each code bit compares two neighbouring bits of i.

SWE Reasoning

Spot it

The statement asks for all 2 ** n bit patterns in an order where neighbours differ in exactly one bit.
The statement asks for the position of a pattern in that order, or the pattern at a position.
A hardware or puzzle story needs a change of one bit at a time: a rotary encoder, a lock with switches, a walk over the corners of a cube.
A first idea is backtracking over all patterns. That works, but a formula gives the list in O(2^n) with no search.

The invariant, step by step

Start with codes = []. After 0 rounds it holds 0 codes, which is correct.
In round i, i >> 1 puts bit k + 1 of i at place k.
i ^ (i >> 1) is 1 at place k exactly when bits k and k + 1 of i differ.
The step from i to i + 1 flips bits 0 to t of i. Every pair inside that range keeps its answer, and only the pair at places t and t + 1 changes.
So the new code differs from the previous code in exactly one bit.
After 2 ** n rounds, codes holds every value from 0 to 2 ** n - 1 once, in Gray order.

Traps

range(n) instead of range(1 << n). n is the number of bits. For n = 3 the list has 3 codes where 8 are needed.
range(1, 1 << n). The list leaves out the code for position 0. For n = 2 it is [1, 3, 2] and does not start at 0.
| instead of ^. OR gives 1 where either bit is 1, so two positions can share a code. For n = 2 the value 2 is never produced.
i ^ (i << 1). A left shift moves bits up, so the code compares bit k with bit k - 1. The list grows past 2 ** n - 1 for most i, and the values are not in the range 0 to 2 ** n - 1.

Practice

Canonical LeetCode:Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)