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
def grayCode(self, n: int) -> List[int]:
length = 1 << n # same as 2**n
visited = [False] * length
def dfs(start_index, code):
if start_index == length:
return True
for i in range(n):
new_code = code ^ (1 << i)
print(new_code)
if not visited[new_code]:
path.append(new_code)
visited[new_code] = True
if dfs(start_index+1, new_code): return True
visited[new_code] = False
path.pop()
return False
path = [0]
visited[0] = True
dfs(1, 0)
return path
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorHow does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!