[TOC] ## Solution --- #### Overview According to [Wikipedia](https://en.wikipedia.org/wiki/Gray_code) the reflected binary code (RBC) or Gray code, named after Frank Gray, is an ordering of the binary numeral system such that two successive values differ by only one bit (binary digit). The Gray code sequence for `n = 3` bit numbers is: `[000, 001, 011, 010, 110, 111, 101, 100]`. The difference in decimal, binary, Gray code sequence can be better understood using this table: ![fig](../Figures/89/89_Gray_Code_Table.png) *Figure 1. The decimal, binary, Gray code, Gray decimal sequence generated for n = 3 bits* Next, if you observe the Gray code sequence, you'll find some patterns. For example the $$0^{th}$$ bit (from the right) at every consecutive gray decimal number has the following pattern: `0 1 1 0` (these are the last bits of each number in the Gray Decimal column). Similarly, the $$1^{st}$$ bit at every consecutive Gray Decimal number has the following pattern: `0 0 1 1 1 1 0 0`. If you partition these sequences at their center, you get two sequences that are mirror images of each other. Next, consider the first $$2 ^ 1 = 2$$ numbers, then the first $$2 ^ 2 = 4$$ numbers and so on in the above table. For the first $$2 ^ n$$ numbers, a similar mirror image pattern is visible upon partitioning the sequence into two halves. The first `n - 1` bits (from the right) are mirror images in the two partitions. The most significant bit (MSB) is set to `0` in the numbers of the first half and `1` in the second half. Now that we have observed these patterns, lets look at the implementation (five different approaches). Note that we need to return the numbers in the resulting sequence in decimal form i.e, the answer for `n = 3` will be `[0,1,3,2,6,7,5,4]` (not `[000, 001, 011, 010, 110, 111, 101, 100]`). Also for a particular `n` there can be more than one valid sequence. For example for `n = 2` both of the following sequences are valid : `[00, 01, 11, 10]` and `[00, 10, 11, 01]`. Also, the Gray code sequence of `n` bits will be of length $$2 ^ n$$ and it consists of unique numbers ranging from $$0$$ to $$2 ^ n - 1$$.
--- #### Approach 1: Backtracking **Intuition** If you're not familiar with backtracking, check out our [Explore Card](https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/). In the Gray code sequence, the adjacent numbers in the sequence should differ by only one bit (binary digit). Also, we know that the Gray code sequence always starts with $$0$$. As a brute force solution, we can start a Depth First Search from the number $$0$$. For a given number, we will try all possibilities i.e, we continue with all possible numbers which satisfy two conditions: 1. They are not a part of the current sequence. 2. Their binary representation differs from the current number by exactly one bit. We will stop our search when no number satisfies the above conditions or when the length of the sequence reaches $$2 ^ n$$ where `n` is the total number of bits in the code (`n` bits will produce $$2 ^ n$$ length sequence). **Algorithm** 1. Initialize a `result` list to store the solution sequence. Add `0` to the list before calling the helper method as all gray code sequences start with `0`. 2. Initialize a set `visited`. This keeps track of the numbers present in the current sequence to prevent repetition. 3. Start with the number `0`. 4. In the `grayCodeHelper()` function, use a `for` loop to find each possible number (`next`) that can be generated by changing one bit of the last number in the `result` list (`current`). We do so by toggling the $$i^{th}$$ bit at each iteration. Since the maximum possible number of bits present in any number of the sequence is `n`, we need to toggle `n` bits. 5. If `next` is not present in the set of used numbers (`isPresent`) add it to the `result` list and the `isPresent` set. 6. Continue the search with `next`. - If `grayCodeHelper(next)` returns true, it means we have found a valid sequence. So no further search is required (**early stop**). This early termination improves the runtime. - If no valid sequence is found with `next`, we remove it from the `result` list and the `isPresent` set and continue our search. 7. Upon reaching the base condition, when the length of the current sequence is $$2 ^ n$$, return `true`. 8. Exiting the `for` loop implies no valid Gray code sequence was found with `current` as the last number. So return `false`. **Implementation** **Complexity Analysis** Here $$n$$ is the total number of bits in the Gray code. * Time complexity: $$O(n* 2 ^ n)$$ For $$n$$ bits $$2 ^ n$$ numbers are possible. The maximum depth of the recursive function stack is $$2 ^ n$$ (The recursion stops when the size of `result` list is $$2 ^ n$$). In our backtracking algorithm, at every function call we iterate over a loop of length $$n$$ and try to find out all possible successors of the last added number in the present sequence. We continue our search with the first value that succeeds (not present in the `isPresent` set). Since we are using `HashSet` and `unordered_set` which have an amortized runtime of $$O(1)$$ in all operations, use of sets doesn't increase the time complexity. Another key observation is that in this particular problem the program never backtracks and always finds a path forward. We can check this by executing the solution after removing the following lines from our code: ``` isPresent.erase(next); result.pop_back(); ``` This means that greedily changing the right-most bit that does not result in a number already in `result`, will always lead to the solution. However, we would not know that beforehand while we are coming up with the solution, so we have to assume that backtracking may be needed should something not work out. So in theory the runtime is $$O(2^n)!$$ but in practice, it comes out to $$O(n * 2 ^ n)$$. * Space complexity: $$O(2 ^ n)$$ We use a set `isPresent` which will contain at most $$2 ^ n$$ numbers. The space occupied by the output `result` is not considered in the space complexity analysis.
--- #### Approach 2: Recursion **Intuition** If you're not familiar with recursion, check out our [Explore Card](https://leetcode.com/explore/learn/card/recursion-i/). Consider the sequence generated for `n = 0 to 3`. For `n = 0` the Gray code sequence is `[0]`. For `n = 1` the Gray code sequence is `[0, 1]`. Similarly, we had `[0, 1]` from `n = 1` and for `n = 2` the Gray code sequence is `[00, 01, 11, 10]`. By observing the sequences generated with n = 0, 1, 2.... we will find a pattern. We can obtain the Gray code sequence for `n` from the Gray code sequence for `n - 1`. For example the Gray code sequence for `n = 3` is `[000, 001, 011, 010, 110, 111, 101, 100]` (`G(3)`). This sequence can be obtained from the sequence `[00, 01, 11, 10]`(say `G(2)`) for `n = 2` as follows : 1. Add `0` to the $$(n - 1)^{th}$$ position (0 based indexed, the $$2^{nd}$$ bit from the right) to the entire sequence of `G(2)`. `[00, 01, 11, 10]` -> `[000, 001, 011, 010]` (`G(3a)`). 2. Reverse `G(2)` sequence and add `1` (`1 << n - 1`) to the $$(n - 1)^{th}$$ position (the $$2^{nd}$$ bit from the right) `[00, 01, 11, 10]` -> `[10, 11, 01, 00]` -> `[110, 111 101, 100]` (`G(3b)`). 3. Concatenate `G(3a)` and `G(3b)` to get the Gray code sequence for `n = 3` (`G(3)`) : `[000, 001, 011, 010, 110, 111, 101, 100]` This can be better understood with the following animation. !?!../Documents/89_Gray_Code.json:960,540!?! **Algorithm** 1. Initialize a list `result` which will return the Gray code sequence for the value of `n`. 2. Use a recursive helper function `grayCodeHelper` and pass the `result` list as a reference. 3. At base condition (`n = 0`) add the number `0` to `result` and return. This is because the Gray code sequence starts with `0`. 4. As demonstrated in the intuition section, we can derive the sequence for `n` from the sequence for `n - 1`. So make a recursive call to `grayCodeHelper` function with `n - 1`. 5. Set the bit at $$(n - 1)^{th}$$ position and assign it to a variable `mask`. `mask` is used to set the $$(n - 1)^{th}$$ bit from the least significant bit (LSB) of all the numbers present in the current list `result`. 6. Iterate backward over the `result` list. 7. Set the $$(n - 1)^{th}$$ bit of the $$i^{th}$$ number and add the new number formed to the `result` list. Thus, the size of the `result` list will double. 8. The `result` list contains a valid Gray code sequence for the current given number of bits. Return the `result` list. **Implementation** **Complexity Analysis** Here $$n$$ is the total number of bits in the code. * Time complexity: $$O(2 ^ n)$$ The maximum depth of the recursive function stack is $$n$$. At every function call we iterate over the list `result` and at each iteration we add a new number to the sequence. At $$n = 0$$ the size of the list is $$1$$. At $$n = 1$$ we iterate over the list $$[0]$$ of size $$2 ^ 0 = 1$$. Next, at $$n = 2$$ we iterate over the list $$[0, 1]$$ of size $$2 ^ 1 = 2$$. Likewise, at $$n = 3$$ we iterate over the list $$[0, 1, 3, 2]$$ of size $$2 ^ 2 = 4$$. This ends at $$n$$ where we iterate over a list of size $$2 ^ {n - 1}$$. The mathematical expression for the above analysis reflects a geometric progression as follows $$1 + 2 + 4 + 8 + ......2 ^{n - 1}$$. Thus the time complexity will be $$O(2 ^ n)$$. * Space complexity: $$O(n)$$ We start from $$n$$ and continue our recursive function call until our base condition $$n = 0$$ is reached. Thus, the depth of the function call stack will be $$O(n)$$. All $$2 ^ n$$ numbers are added to the same list. At every function call, we iterate over the list, and at each iteration, we add a new number to the sequence. Thus, the size of the list `result` at the end of a function call is twice its size at the previous function call. The space occupied by the output `result` is not considered in the space complexity analysis.
--- #### Approach 3: Iteration **Intuition** The concept used in Approach 2 can be applied iteratively. The iterative method of generating `G(n)` from `G(n - 1)` involves using two for loops instead of making recursive calls to find `G(n - 1)`. Recall that `G(n)` is the Gray code sequence consisting of numbers between $$0$$ to $$2 ^{n - 1}$$. We iteratively find `G(n - 1)` first. Then we add the prefix $$0$$ to each digit of `G(n - 1)`. Next, we reverse `G(n - 1)` and add the prefix $$1$$ to each digit of the reversed `G(n - 1)` sequence. Finally, combining the above two sequences gives us `G(n)`. **Algorithm** 1. Initialize an empty list `result` and add $$0$$ to it. 2. Since the Gray code sequence for $$i$$ bits (`G(i)`) can be constructed from the Gray code sequence for $$i - 1$$ bits (`G(i - 1)`), we run a for loop from $$\text{i} \hspace{3pt} = 1 \hspace{3pt} \text{to} \hspace{3pt} n$$ to find Gray code sequences with increasing bits. - At each iteration, we set the bit at $$(i - 1)^{th}$$ position and assign it to a variable `mask`. `mask` is used to set the $$(i - 1)^{th}$$ bit from the LSB of all the numbers present in the current sequence `result` (`G(i - 1)`). - Iterate backward over the current sequence `result`. Add prefix $$1$$ (`mask`) to each number present in `result`. 3. Return `result` which represents the Gray code sequence with `n` total bits. **Implementation** **Complexity Analysis** Here $$n$$ is the total number of bits in the Gray code. * Time complexity: $$O(2 ^ n)$$ One insight regarding the time complexity is that in the iterative algorithm, we are building the list in a deterministic and non-redundant way. This means that there is no backtracking, each iteration will produce a series of valid elements in the final sequence. Since the total number of elements in the final sequence is $$2 ^ n$$, it will take a total of $$2 ^ n$$ steps to produce the sequence. Here the outer loop runs from $$i = 1 \hspace{3pt} \text{to} \hspace{3pt} n$$. At $$i^{th}$$ step the length of the `result` list is $$2 ^ {i - 1}$$. So the number of iterations at $$n = 1$$ is $$1$$, at $$n = 2$$ is $$2$$, $$n = 3$$ is $$4$$ and so on. Similar to Approach 2 the mathematical expression for the above analysis reflects a geometric progression as follows $$1 + 2 + 4 + 8 + ... + 2 ^{n - 1}$$. Thus the time complexity will be $$O(2 ^ n)$$. * Space complexity: $$O(1)$$ The space occupied by the output `result` is not considered in the space complexity analysis. So overall no extra space is required in this approach.
--- #### Approach 4: Recursion 2 **Intuition** This is an alternate recursion-based solution. We use a global variable `nextNum` which we update during specific recursive calls (every terminating condition) to obtain the Gray code sequence. We initialize `nextNum` as 0. Assuming we start with `n`, we call the function recursively with `n - 1` until `n = 0` (i.e. the $$0^{th}$$ bit). At `n = 0`, we add the value of `nextNum` to `result`. We then flip the bit at the $n - 1^{th}$ position from the right and again call the function until we reach the base condition (`n = 0`). Thus, the numbers get added to `result` only at the base condition. To think of this intuitively in a top-down manner, if n is the MSB, then we want n to be 0 first and then 1. First, we set it to 0, then make recursive calls so smaller bits (n - 1 through 0) get resolved, then set this MSB to 1, and repeat the process so lower bits get re-set to their correct values. The recursion tree depicts a complete binary tree. For `n` bits, the height of the tree will be `n + 1` and the total number of nodes in it will be $$2^{n + 1} - 1$$. Each node represents one function call. There will be $$2^{n}$$ leaf nodes and at these leaf nodes, the actual values of the gray code sequence will be added to the `result`. Traversing the leaf nodes from left to right will give us the Gray code sequence for `n` bits. This can be better understood with the below diagram. The black arrow indicates the value of `nextNum` while making forward recursive calls and the red arrow indicates the value of `nextNum` while returning to each internal node. ![fig](../Figures/89/89_Gray_Code_Tree.png) *Figure 2. The recursion tree for n = 3 bits* The figure shows the program flow for `n = 3` bits. Roughly, the steps followed here are as follows: - Start with `n = 3`, `nextNum` = `000` - Solve for `n = 2` - Solve for `n = 1` - Solve for `n = 0`. Add `000` (`0`). - Flip 0th bit. `nextNum` = `001`. - Solve again for `n = 1` - Solve for `n = 0`. Add `001` (`1`). - Flip 1st bit. `nextNum` = `011` - Solve again for `n = 2` - Solve for `n = 1` - Solve for `n = 0`. Add `011` (`3`). - Flip 0th bit. `nextNum` = `010`. - Solve again for `n = 1` - Solve for `n = 0`. Add `010` (`2`). - Flip 2nd bit. `nextNum` = `110`. - Solve again for `n = 3` (Repeat the above steps for `n = 3`, exactly once more with nextNum set to `110`. Note that this time, it will go in the reverse order since we're starting with `10` as opposed to `00` for the last 2 digits) **Algorithm** 1. Take a global variable `nextNum` and initialize it to `0`. 2. Recursively call the `grayCodeHelper` function till the base condition (`n = 0`) is reached. 3. On reaching the base condition add the current value of `nextNum` to the `result`. 4. Inside the `grayCodeHelper` function for `n`, flip the $$(n - 1)^{th}$$ bit of nextNum. Go to step 2 and continue. 5. Return the `result` from the `grayCode` function. **Implementation** **Complexity Analysis** Here $$n$$ is the total number of bits in the code. * Time complexity: $$O(2 ^ n)$$ The above diagram illustrates the recursion tree. If we consider each node as a block of statements executed at each recursive function call, the total time complexity will be in terms of the number of nodes present. For $$n$$ bits the total number of nodes (internal + leaf) is $$2 ^ {n + 1} - 1$$. So the overall time complexity is $$O(2 ^ {n + 1} - 1)$$ = $$O(2 ^ n)$$. * Space complexity: $$O(n)$$ From the diagram, we can conclude that the maximum depth of the function call stack will be $$n + 1$$. So the space complexity will be $$O(n)$$. The space occupied by the `result` is not considered in the space complexity analysis.
--- #### Approach 5: Iteration with a single loop **Intuition** This solution is inspired by a [post](https://leetcode.com/problems/gray-code/discuss/29881/An-accepted-three-line-solution-in-JAVA) written by a fellow LeetCode user and [Wikipedia](https://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code). Unlike the previous iterative approach, this approach uses a single loop to calculate all the Gray code sequence numbers. This solution would be very challenging to come up with during an interview without prior knowledge. We have included it here for completeness because it is optimal in terms of the overall complexity. For some problems, by comparing the input values to the expected output values, we can identify a pattern or a relationship between the two that allows us to calculate the output values in a more efficient way. In this case, we first need to solve the problem using one of the previously discussed, more intuitive, approaches to get the expected Gray code value at each index. Afterwhich, we can search for a pattern that relates each index to the Gray code value at that index. Take a minute to look at the table provided in the overview of this article. Can you spot the relationship between index, `i`, and the Gray code value, `G(i)`? This approach is outside the expectations of a normal interview because the pattern is very difficult to identify. Let's see what happens if we take the XOR of `i` and `G(i)`. ![fig](../Figures/89/89_Gray_Code_Table2.png) *Figure 3. Table illustrating the XOR of `i` and `G(i)`* Notice that $$i \oplus G(i)$$ always equals $$i / 2$$, where $$\oplus$$ signifies XOR and $$i / 2$$ uses floor division. Rearranging the equation, we can say that $$G(i) = i \oplus (i / 2)$$ or equivalently $$G(i) = i \oplus (i >> 1)$$. If this pattern is always true, then we can calculate the Gray code value for each index in constant time. How do we know if this pattern will always be true? At first glance, this formula might not seem very convincing. Thus we will test its validity before proceeding to the implementation. To validate this formula we need to prove two things: 1. `G(i)` and `G(i + 1)` differ by exactly one digit. $$ \begin{aligned} G(i) \oplus G(i + 1) &= (i \oplus (i >> 1)) \oplus ((i + 1) \oplus ((i + 1) >> 1))\\ &= i \oplus (i >> 1) \oplus (i + 1) \oplus ((i + 1) >> 1) \hspace{3pt} \text{XOR} \hspace{3pt} \text{is} \hspace{3pt} \text{commutative}\\ &= (i \oplus (i + 1)) \oplus ((i \oplus (i + 1)) >> 1) \\ &= X \oplus Y (say) \\ \end{aligned}\\ \text{where} \hspace{3pt} X = (i \oplus (i + 1)) \hspace{3pt} \text{and} \hspace{3pt} Y = ((i \oplus (i + 1)) >> 1) $$ Adding 1 to any number is equivalent to toggling every bit from the rightmost zero bit to the end. Let's use $$87 + 1 = 88$$ as an example: $$1010111 + 0000001 = 1011000$$. Notice that the $$0^{th}$$ through $$3^{rd}$$ bits are flipped while all the other bits remain the same. Thus in general if $$i = ...#01...1 , i + 1$$ will be $$...#10...0$$. Here $$#$$ represents the first bit to the left of the rightmost zero bit and `...` represents any sequence of binary digits. As we can observe the length of the tailing $$1$$ bits of $$i$$ will be the same as the length of the tailing $$0$$ bits of $$i + 1$$. The bits from the beginning upto # will remain the same in both $$i$$ and $$i + 1$$ and the bits after # will be opposite in $$i$$ and $$i + 1$$. Thus we can show that xor product of $$i$$ and $$i + 1$$ will be of the form $$0000000111111$$ (sequence of zeros followed by a sequence of ones): $$ \begin{aligned} X = i \oplus (i + 1) &= 0000000111111\\ Y = ((i \oplus (i + 1)) >> 1) &= 0000000011111 \\ X \oplus Y &= 0000000100000\\ \end{aligned} $$ From the above observation we can say that $$G(i) \oplus G(i + 1) = X \oplus Y$$ differs in only one bit. 2. No number is repeated in the sequence i.e, `G(i)` is bijective, `G(i) = G(j)` if and only if `i = j`. $$ \begin{aligned} \text{Let} \hspace{3pt}G(i) = i \oplus (i >> 1) \hspace{3pt} \text{and} \hspace{3pt} G(j) = j \oplus (j >> 1) \\ \end{aligned}\\ \text{If} \hspace{3pt} G(i) = G(j) \hspace{3pt} \text{then}\\ $$ $$ \begin{aligned} &=>G(i) \oplus G(j) &= 0 \\ &= (i \oplus (i >> 1)) \oplus (j \oplus (j >> 1)) &= 0 \\ &= (i \oplus j) \oplus ((i \oplus j) >> 1) &= 0\\ \end{aligned}\\ \text{Let} \hspace{3pt} X = i \oplus j = b^{n - 1} b^{n - 2} ... b ^{0} $$ $$\text{(binary }\hspace{3pt}\text{representation} \hspace{3pt}\text{of} \hspace{3pt}\text{the} \hspace{3pt}\text{XOR} \hspace{3pt}\text{product)} \hspace{3pt}\\ X >> 1 = 0 b^{n - 1} b^{n - 2} ... b ^{1}\\ \text{If} \hspace{3pt} X \oplus (X >> 1) = 0 \\ => (b^{n - 1} b^{n - 2} ... b ^{0}) \oplus (0 b^{n - 1} b^{n - 2} ... b ^{1}) = 0\\ \text{On} \hspace{3pt}\text{doing} \hspace{3pt}\text{bitwise} \hspace{3pt}\text{comparison} ,\\ b^{n - 1} \oplus 0 = 0 => b^{n - 1} = 0\\ b^{n - 2} \oplus b^{n - 1} = 0 => b^{n - 2} = 0\\ b^{n - 3} \oplus b^{n - 2} = 0 => b^{n - 3} = 0\\ .\\ .\\ . \\ b ^{0} \oplus b^{1} = 0 => b^{0} = 0\\ \text{Thus} \hspace{3pt} X = i \oplus j = b^{n - 1} b^{n - 2} ... b ^{0} = 0 \\ \text{We} \hspace{3pt} \text{can} \hspace{3pt} \text{conclude} \hspace{3pt} \text{that} \hspace{3pt} i \oplus j = 0 => i = j\\ $$ Thus the sequence generated by $$G(i)$$ consists of unique numbers. **Algorithm** 1. Initialize `sequenceLength` variable to $$2^n$$. `sequenceLength` denotes the total number of elements present in the Gray code sequence. 2. Run a for loop for $$i = 0 \hspace{3pt} \text{to} \hspace{3pt} 2^n$$. - At each iteration calculate the next number to be added in the sequence using the formula $$G(i) = i \oplus (i >> 1)$$ and assign it to `num`. - Add `num` to the `result`. 3. Return `result` list. **Implementation** **Complexity Analysis** Here $$n$$ is the total number of bits in the Gray code. * Time complexity: $$O(2 ^ n)$$ We use a single for loop to add all the $$2^n$$ numbers of the Gray code sequence to the `result`. Thus the time complexity will be $$O(2 ^ n)$$. * Space complexity: $$O(1)$$ The space occupied by the output `result` is not considered in the space complexity analysis. So overall no extra space is used in this approach.
---

Gray Code

Problem Description

Problem Description

Answer Panel