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.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name