# Gray Code #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. The gray code is a binary numeral system where two successive numbers differ in only one bit.2. Given a non-negative integer n representing the total number of bits in the code, print the      sequence of gray code. A gray code sequence must begin with 0.  Example: Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2 [0,2,3,1] is also a valid gray code sequence. 00 - 0 10 - 2 11 - 3 01 - 1`
Input Format
`First line contains n(number of digits).`
Output Format
`Return the list of numbers in any valid order.`
Question Video
Constraints
`0<=n<=20`
Sample Input
`2`
Sample Output
`[0, 1, 2, 3]`

• Editorial

The problem here deals with printing the gray code representation for the n-bit numbers. Say for n = 2 we would have [ 0, 1, 3, 2 ].

A gray code representation is a way of representing numbers in which the consecutive numbers can have a bit difference of 1. So for n = 2 [ 00, 01, 10, 11 ] would not work as for {01} and {10} there is a bit difference of 2. Therefore the code is [ 00, 01, 11, 10 ] => [0, 1, 3, 2] which maintains consistency.

The problem can be solved using recursion. For better clarity let's take an example: Suppose we want to have a 3 - bit gray code representation using a 2-bit representation which we know is [ 00, 01, 11, 10 ] so to get 3 - bit representation firstly we need to add a bit to the given set.

1. Adding 0-bit value at MSB -  [ 000, 001, 011, 010 ] Now we can see that adding 0 at MSB has not been an issue as every consecutive number has a bit difference of 1.

2. Adding 1-bit value at MSB -  [ 100, 101, 111, 110 ] Now also we can see that adding 1 at MSB has not been an issue as every consecutive number has a bit difference of 1.

The problem occurs when we combine both the sets as at that point {010} and {100} conflicts with bit difference equals 2.

To eradicate this issue all we need to do is to reverse the set with MSB 1 then we would get a consistent result. Along with the power of recursion, we can build gray code for varying range of bits. As for every case we first need to add 0 to the recursive result and then we need to add 1 in reverse order and later combine the two.

Below is the recursive tree for N = 3 :  Time Complexity: O(n)

The time complexity for the function is linear as we are calling recursively for every bit range.

Space Complexity: O(n)

The space complexity for the function is linear as we are maintaining an ArrayList to store our result in addition to the recursive stack space complexity.

• Related Topics

Run

Run
Id Name