Gray Code

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’)

1. Let’s consider ‘N' : 3 and we have solution of ‘N-1' : 2 : { ‘00’, ‘01’, ‘10’, ‘11’} and called it ‘PRE’.
2. Create a new list/vector of ‘PRE’ in reverse order { ‘11’, ‘10’, ‘01’, ‘00’ } called it ‘NEW’.
3. Add ‘0’ as a prefix, in all the elements of ‘PRE’ : { ‘000’, ‘001’, ‘010’, ‘011’ } /
4. Add ‘1’ as a prefix, in all the elements of ‘NEW’ : { ‘111’, ‘110’, ‘101’, ‘100’} .
5. Concatenate the ‘PRE’ + ‘NEW’ and it will be answered for ‘N' : 3.
6. Return a number conversion of new concatenated ‘list/vector’.

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 :

1. Base case : If ‘N’ is equal to 0.
   • Return { ‘0’ }.
2. If ‘N' is equal to 1
   • Return { ‘0’, ‘1’ }.
3. 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’.

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 :

1. Create a list/vector (say, ‘DP’) to store the answer of size 2^'grayNumber'.
2. ‘DP’[1] =1.
3. Run a loop from 2 to 2^'grayNumber-1’ (say, iterator ‘i’)
4. 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’
5. Finally, return ‘DP’.

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 :

1. Create an array (say, ‘ANSWER’) which will store the numbers.
2. 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’.