Home » Interview coding problems/challenges

Generate Gray Code Sequences

In this article, we are going to see how to generate gray code sequence of length n? This problem has been featured in interview rounds of Amazon, Microsoft.
Submitted by Radib Kar, on March 01, 2019

Problem statement:

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

Solution:

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