Q:

# Given a number N, write a function which generates all n-bit gray code sequences, a gray code sequence is a sequence such that successive patterns in it differ by one bit

Given a number N, write a function which generates all n-bit gray code sequences, a gray code sequence is a sequence such that successive patterns in it differ by one bit.

Example:

```    Input:
N=2
Output:
00 01 11 10

Input:
N=3
Output:
000 001 011010 110 111 101 100
```

### All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Construction an n bit gray code follows a robust algorithm. The binary-reflected Gray code list for n bits can be generated recursively from the list for n − 1 bits by reflecting the list (i.e. listing the entries in reverse order), prefixing the entries in the original list with a binary 0, prefixing the entries in the reflected list with a binary 1, and then concatenating the original list with the reversed list.

Reference: Gray_code

### Algorithm to generate n bit gray code list

1. Let, the n-1 length gray code list has m elements, (m=2^(n-1))
2. Create list1 by adding prefix 0 to all the m elements
3. Create list2 by adding prefix 1 to all the m elements
4. New list for n-bit gray code= list1+reverse(list)
5. New list size 2m (2^n)

For any n bit gray code list, we start with gray code list of length 1 (elements are only '0' and '1'). Then iterate till finding n-bit gray code list.

The above can be explained with help of an example,

```    Let we need to find gray code sequence for n=3
//Base case
For n=1
List: 0, 1

For n=2
Add prefix '0' to create list1
List1= 00, 01
Add prefix '1' to create list2
List2= 10, 11
New list=list1 + reverse(list2)
=00, 01, 11, 10 //List for n=2

For n=3
Add prefix '0' to create list1
List1= 000, 001, 011, 010
Add prefix '1' to create list2
List2= 100, 101, 111, 110
New list=list1 + reverse(list2)
=000, 001, 011, 010, 110, 111, 101, 100 //List for n=3
```

C++ implementation

``````#include <bits/stdc++.h>
using namespace std;

string get_string(char c)
{
string s(1,c);
return s;
}

void generateCode(int n)
{
if(n<=0){
cout<<"invalid input\n";
return;
}

vector<string> a,temp;
a.push_back("0");
a.push_back("1");

for(int i=0;i<n-1;i++){
for(int j=0;j<a.size();j++){
temp.push_back(get_string('0')+a[j]);
}
for(int j=a.size()-1;j>=0;j--){
temp.push_back(get_string('1')+a[j]);
}
a=temp;
temp.clear();
}

for(int i=0;i<a.size();i++)
cout<<a[i]<<"\n";
}

int main(){
int n;

cout<<"Enter n:\n";
cin>>n;

cout<<"Printing gray codes for "<<n<<" bit\n";
generateCode(n);

return 0;
}
``````

Output

```First run:
Enter n:
3
Printing gray codes for 3 bit
000
001
011
010
110
111
101
100

Second run:
Enter n:
4
Printing gray codes for 4 bit
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000 ```

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)