Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 – 0
01 – 1
11 – 3
10 – 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 – 0
10 – 2
11 – 3
01 – 1
Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].
Before solving this problem, let us understand what grey code is.
Before knowing about grey code, we shall understand about binary format.
Below are some numbers and their binary representation:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
If we check the difference in bits between 2 consecutive number will be as follows:
The difference in bits between 0 and 1 is 1. Because only left most bit is changed.
The difference in bits between 1 and 2 is 2. Because 2nd digit changed from 0 to 1 and third digit is changed from 1 to 0.
Similarly, the difference in bits between 3 and 4 is 3. Because all the 3 digits have been changed.
In computer this is a problem, hence we use grey code system. In grey code system the difference between any 2 consecutive numbers will always be 1.
So to write grey code, we start with 000.
000
001
011
010
110
111
101
100
In the above list, the difference between any 2 consecutive digits is only 1 bit difference.
Hence according to our question, “n” represents the number of bits in the code.
For n = 2, the grey code can be written as below:
As grey code starts from 00,
00
01
11
10
If we convert them into decimal format, it will be [0, 1, 3, 2]. Hence the solution.
To get the grey code of Nth element, we use below formula:
N ^ floor(N/2)
Solution in C++
/*
* File : grey_code.cpp
*/
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
std::vector<int> get_grey_code(int n)
{
vector <int> result;
if (n == 0)
{
result.push_back(0);
return result;
}
for (int i = 0; i < pow(2, n); i++)
{
result.push_back(i ^ (i / 2));
}
return result;
}
int main()
{
int n = 2;
vector<int> result = get_grey_code( n );
for (int i = 0; i < result.size(); ++i)
{
cout<< " "<< result[i]<<endl;
}
}Output:
0
1
3
2