Grey Code
An n-bit gray code sequence is a sequence of 2n
integers where:
- Every integer is in the inclusive range
[0, 2n - 1]
, - The first integer is
0
, - An integer appears no more than once in the sequence,
- The binary representation of every pair of adjacent integers differs by exactly one bit, and
- The binary representation of the first and last integers differs by exactly one bit.
Given an integer n
, return any valid n-bit gray code sequence.
Example 1:
Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2]
is [00,01,11,10]
.
00
and01
differ by one bit01
and11
differ by one bit11
and10
differ by one bit10
and00
differ by one bit
[0,2,3,1]
is also a valid gray code sequence, whose binary representation is [00,10,11,01]
.
00
and10
differ by one bit10
and11
differ by one bit11
and01
differ by one bit01
and00
differ by one bit
Example 2:
Input: n = 1
Output: [0,1]
Constraints:
1 <= n <= 16
Solution
In this question, we are dealing with binary representation of integers, we will be using bit manipulation. To learn more, checkout Bitmask Intro.
The two important operations we will use are the shift operator (<<
) and the XOR (exclusive or) operator (^
).
1 << i
: will shift1
byi
bits to the left, the new binary number will havei
zeros after a1
.code ^ (1 << i)
: flips thei
th bit (from the right) incode
's binary representation. By the property of XOR that0^1 = 1
and1^1 = 0
.
Now, we can use these two operations to find the candidates for the next code. And since we are only looking for one solution, we can use the aggregation template to return earlier. We will apply the backtracking2 template and fill in the logic.
is_leaf
:start_index == 2**n
, we have used all integersget_edges
:new_code = code ^ (1 << i)
where0 <= i < n
, thisnew_code
has one flipped bit on thei
-th bit, it can potentially be the next codeis_valid
:new_code
is valid when we have not used it (not in visited
)
Implementation
1def grayCode(self, n: int) -> List[int]:
2 length = 1 << n # same as 2**n
3 visited = [False] * length
4
5 def dfs(start_index, code):
6 if start_index == length:
7 return True
8 for i in range(n):
9 new_code = code ^ (1 << i)
10 print(new_code)
11 if not visited[new_code]:
12 path.append(new_code)
13 visited[new_code] = True
14 if dfs(start_index+1, new_code): return True
15 visited[new_code] = False
16 path.pop()
17 return False
18
19 path = [0]
20 visited[0] = True
21 dfs(1, 0)
22 return path
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.