"A road is never long if you have the courage to stand and walk."

Gray Code

Introduction:

Welcome back, dear reader. So, how is it going with bit-manipulation till now? In this article, we
will learn a very interesting binary code representation of numbers called GRAY CODE. So, let us
first talk about the gray code and understand what is the concept behind it. Have a look at the
image shown below:

In the above image, we have shown the gray codes for the numbers 0 to 7. Notice the difference
between the binary representation and the gray code representation. What do you notice? See, the
gray codes differ by only one bit whereas the binary codes may differ by more than one bit. What do
we mean by this? Have a look at the image shown below:

We can clearly see that two consecutive binary numbers can have a difference of one or more than one
bit but two consecutive gray codes will always have a difference of only one bit between them.
Now that you have an idea about the gray codes, let us discuss the question that we have. In the
question, we will be given an integer as the input. Let us say the input that we get is 2. For that,
we have to print an arraylist of integers. For instance, if we get 2 as the input, the output will
be: [0,1,3,2]. Why? Let us talk about it.
So, if 2 is the input, this means that we have to generate all the 2 bit gray codes. The two bit
gray codes are shown below:

So, we have generated all the two bit gray codes and we have kept them in an arraylist of integers.
Now, we will assume that the array list is not filled with gray codes, rather we will assume that
this is the binary representation given to us. So, if we convert these numbers into decimal numbers,
we will get an arraylist as shown in the figure:

So, we hope that you have understood the concept of gray codes and have also understood the
question. If you have any doubts about any of these things, refer to the GRAY CODES VIDEO this to
understand the question completely and also understand the concept of gray codes. So, we recommend
you try to solve this problem first and then go to the solution

Let us solve this problem in a different way. We will give you the code for the problem first and
then we will analyze how the code is working.

Java Code

import java.util.*;
public class Main {
public static List grayCode(int n) {
List< Integer> ans = new ArrayList< >();
if (n == 0) {
ans.add(0);
return ans;
}
backtrack(ans, n);
return ans;
}
static int temp;
private static void backtrack(List ans, int n) {
if (n == 0) {
ans.add(temp);
return;
}
backtrack(ans, n - 1);
temp = temp ^ (1 << (n - 1)); backtrack(ans, n - 1); } public static void
main(String[] args) { Scanner scn=new Scanner(System.in); List
ans=grayCode(scn.nextInt());
Collections.sort(ans);
System.out.println(ans);
}
}

java;
true";

So, dear reader, let us try to analyze this code now. We have a grayCode(n) function which we have
called in the main function. So, when the call is made to the grayCode(n) function (say for n=2)
then in the stack we will have the value of n=2.
Also, we enter the function grayCode(n) and a new arraylist "ans" is created. After this, we check
whether n is 0 or not, since it is not zero, this section of code is not executed

Then a call is made to the backtrack function. Again, in the backtrack function, there is a
condition for checking whether n is zero or not. Since n is not zero right now, this section of the
code in the backtrack(ans,n) function does not execute. The next is the call for backtrack(ans,n-1).
This means that now we have n-1=2-1=1 at the top of the stack

Again, we are inside the backtrack(ans,n) function but now n=1. So, the conditional statement will
not execute and we will again call the backtrack function for n-1. This means that the value of n is
now 0

Now n=0. So, the conditional statement will execute and we will add temp to the ans arraylist. Since
temp was declared as static, it's initial value is 0. So, 0 gets added to the arraylist

Now we are back to n=1. Here, the first line of the code was already executed. So, we executed the
second line and temp was calculated. The previous value of temp is 0. When we do 1<<(n-1), this is
equivalent to 1 x 2(n-1) i.e. 1 x 20=1. When we do the XOR of this 1 with the previous value of
temp, we will get 1. So, temp=1. Now again a call is made to n-1. Here n=0 is again at the top
of the stack and we add temp=1 to the ans arraylist.

After this, n=0 wipes out from the stack. Also, n=1 wipes out from the stack too since all
its lines were executed. So, now we are at n=2.

The first call has already executed food n=2. Now, we have to calculate the value of temp.
The previous value of temp is 1 and the value of 1<<(n-1) this time will be 1<<(1)=1 x 21=1
x 2=2. So, when we take the XOR of 1 and 2, we get 3. So, temp=3. Now again a call will
be made to backtrack(ans,n-1) and we will have 1 at the top of the stack..

Again, the call will be backtrack(ans,n-1) and we will have 0 at the top of the
stack. Since n=0, we will add temp=3 to the ans arraylist.

So, dear reader, we will continue this process and we will get an arraylist filled
with gray code sequence. We recommend you try to trace the remaining procedure
yourself. With this, we have completed this problem.

Suggestions

Here are some suggestions from our side that you do not want to miss:

We recommend you try to learn more about gray codes and try to find out where
they are used over binary numbers and what is the importance of the fact that
every gray code number differs only in one bit.

We recommend you try to learn more about gray codes and try to find out where
they are used over binary numbers and what is the importance of the fact that
every gray code number differs only in one bit.