Gray Code
1. The gray code is a binary numeral system where two successive numbers differ in only one bit.Input Format
2. Given a nonnegative 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
First line contains n(number of digits).Output Format
Return the list of numbers in any valid order.Question Video
0<=n<=20Sample Input
2Sample Output
[0, 1, 2, 3]

Editorial
The problem here deals with printing the gray code representation for the nbit 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 2bit 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 0bit 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 1bit 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.

Asked in Companies

Related Topics