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
Which data structure is used to implement priority queue?
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Solution Implementation
How many ways can you arrange the three letters A, B and C?
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
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.