Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2
Before solving this problem, let us understand what grey code is.
Before knowing about grey code, we shall understand about the 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 leftmost bit is changed.
The difference in bits between 1 and 2 is 2. Because 2nd digit changed from 0 to 1 and the 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 a computer this is a problem, hence we use the grey code system. In the 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 the 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++
#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
