Gray Code
Last Updated: 23 Dec, 2020
Difficulty: Moderate
Given a number ‘grayNumber’. Find the gray code sequence.
Conditions for a gray code sequence :
1. Gray code sequence contains numbers from 0 to 2^'grayNumber'-1 in bit/binary form.
2. Two consecutive gray code sequence numbers only differ by 1 bit.
3. Gray code sequence must start with 0.
Example :
Given 'grayNumber' : 2.
As depicted from above image, the gray code sequence is 0,1,3,2.
Note :
1. The output sequence must contain the decimal representation of numbers instead of the binary form.
2. There can be multiple answers print anyone.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains an integer ‘grayNumber’.
Output Format :
For each test case, return the ‘list/vector’ of the Gray code sequence.
The output is ‘Valid’ if returned gray code sequence is correct. Else ‘Invalid’.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 2
0 <= grayNumber <= 15
Time Limit : 1 sec
Approach 1
Suppose are finding an answer for ‘N’ size but we have already the solution for ‘N-1’. then use the previous answer for a new answer. (where ‘N’ is ‘grayNumber’)
- Let’s consider ‘N' : 3 and we have solution of ‘N-1' : 2 : { ‘00’, ‘01’, ‘10’, ‘11’} and called it ‘PRE’.
- Create a new list/vector of ‘PRE’ in reverse order { ‘11’, ‘10’, ‘01’, ‘00’ } called it ‘NEW’.
- Add ‘0’ as a prefix, in all the elements of ‘PRE’ : { ‘000’, ‘001’, ‘010’, ‘011’ } /
- Add ‘1’ as a prefix, in all the elements of ‘NEW’ : { ‘111’, ‘110’, ‘101’, ‘100’} .
- Concatenate the ‘PRE’ + ‘NEW’ and it will be answered for ‘N' : 3.
- Return a number conversion of new concatenated ‘list/vector’.
Approach 2
The approach is to recursively add the 0 and 1 each time until the number of bits is not ‘N' (where ‘N’ is ‘grayNumber’)
Here is the algorithm :
- Base case : If ‘N’ is equal to 0.
- Return { ‘0’ }.
- If ‘N' is equal to 1
- Return { ‘0’, ‘1’ }.
- Call a function SOLVE(grayNumber),
- Then it returns all gray code sequence from 0 to 2^'grayNumber'-1 calls it ‘ANSWER’ list/vector.
- Now generate a gray code sequence for 'grayNumber' + 1
- Add 0 in all the elements of ‘ANSWER’ as a prefix, and called it ‘PRE’.
- Add ‘1’ in all the elements of ‘ANSWER’ in reverse order, as a prefix, and called it ‘NEW’.
- Return concatenated ‘PRE’+’NEW’.
Approach 3
Suppose the current answer for 'N' : 2 is : {0, 1, 3, 2} (where ‘N’ is ‘grayNumber’ ) then add 2*2 in all the elements in reverse order : { 2+4, 3+4, 1+4, 0+4} then our answer for 'N' : 3 will be : {0, 1, 3, 2, 6, 7, 5, 4}.
Why this is working?
Convert {0, 1, 3, 2} in binary bits form {'00', '01', '11', ‘11’} it is the answer for ‘N’ : 2 if we add '0' as prefix and '1' as a prefix in reverse order of binary representation then we get an answer for 'N' : 3. { ‘0’+‘00’, ‘0’+’01’, ‘0’+‘10’, ‘0’+’11’) by adding '0' as the prefix, (‘1’+‘11’, ‘1’+’10’, ‘1’+‘01’, ‘1’+’00’) by adding '1' as the prefix in reverse order }.
You can observe in adding ‘0’ part we are doing nothing because ‘0’ can’t make any change in the number, and adding ‘1’ part is increasing the value of all the elements in reverse order by 2^'N'.
Here is the algorithm :
- Create a list/vector (say, ‘DP’) to store the answer of size 2^'grayNumber'.
- ‘DP’[1] =1.
- Run a loop from 2 to 2^'grayNumber-1’ (say, iterator ‘i’)
- Update ‘DP’[i] as ‘DP’[i-c] + ‘POWER’
- ‘POWER’ is a small nearest 2’s power of ‘i’.
- ‘C’ is reverse iterator will run option direction of ‘i’
- Finally, return ‘DP’.
Approach 4
Since we need only 1 bit change, we can use XOR with 1 bit shifts. With the use of this property and XOR we can generate numbers which differ by 1 bit. Operation : ‘i’ ^ ( 'i' >> 1 ) gives the gray code for ‘i’th number.
Example :
Given ‘N' : 3 ( where ‘N’ is ‘grayNumber’) and let iterator be ‘i’ which iterates from 0 to 2^3 - 1 (7).
Iteration 0 : ‘i’ = 0, ‘i’ ^ ( ‘i’ >> 1 ) = 0 ^ 0 = 0 {000}
Iteration 1 : ‘i’ = 1, ‘i’ ^ ( 'i' >> 1 ) = 1 ^ 0 = 1 {001}
Iteration 2 : ‘i’ = 2, ‘i’ ^ ( 'i' >> 1 ) = 2 ^ 1 = 3 {011}
Iteration 3 : ‘i’ = 3, ‘i’ ^ ( 'i' >> 1 ) = 3 ^ 1 = 2 {010}
Iteration 4 : ‘i’ = 4, ‘i’ ^ ( 'i' >> 1 ) = 4 ^ 2 = 6 {110}
Iteration 5 : ‘i’ = 5, ‘i’ ^ ( 'i' >> 1 ) = 5 ^ 2 = 7 {111}
Iteration 6 : ‘i’ = 6, ‘i’ ^ ( 'i' >> 1 ) = 6 ^ 3 = 5 {101}
Iteration 7 : ‘i’ = 7, ‘i’ ^ ( 'i' >> 1 ) = 7 ^ 3 = 4 {100}
All the numbers generated differ by 1 bit.
Here is the algorithm :
- Create an array (say, ‘ANSWER’) which will store the numbers.
- Run a loop from 0 to 2^'grayNumber' (say, iterator ‘i’)
- Create a variable (say, ‘VAL’) which will denote as the current number to added in the ‘ANSWER’.
- Update ‘VAL’ to ( ‘i’ ^ ('i' >> 1)).
- Insert ‘VAL’ in ‘ANSWER’.
- Finally, return ‘ANSWER’.
