# LC 89 Grey code

The gray code is a binary numeral system where two successive values differ in only one bit.

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.

# Mirror grey code

We want to find a map between binary and grey code. For 1 bit: 0 is mapped to 0, and 1 is mapped to 1. The binary is the same as grey code.

For 2 bits:

``````<br />binary   gery    binary(2)   gery(2)
0         0       00          00
1         1       01          01
____
10          11
11          10
``````

To recursive generate grey code of bit size 2, we will build upon gray code of size 1. We want to generate 4 numbers whose binary representation differ only in 1 bit. If we already have gray code of size n, then if we mirror imaged the gray code, then the upper and lower part are both valid gray code of size(n). To generate gray code 2n, we will just add 0 to the first half and 1 to the second half.

``````class Solution {
public:
vector<int> grayCode(int n) {
vector<string> res = binGrayCode(n);
vector<int> intRes;
for(int i = 0; i < res.size(); i ++){
intRes.push_back(std::stoi(res[i], nullptr, 2));
}
return intRes;
}

vector<string> binGrayCode(int n ){
if(n == 0){
vector<string> vect{"0"};
return vect;
}
if(n == 1){
vector<string> vect{"0", "1"};
return vect;
}
vector<string> firstHalf = binGrayCode(n - 1);
vector<string> mirrorHalf = firstHalf;
reverse(mirrorHalf.begin(), mirrorHalf.end());

for(int i = 0; i < firstHalf.size(); i ++){
firstHalf[i] = "0" + firstHalf[i];
mirrorHalf[i] = "1" + mirrorHalf[i];
}

firstHalf.insert(firstHalf.end(), mirrorHalf.begin(), mirrorHalf.end());
return firstHalf;
}

};
``````

# Iterative approach

``````class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res(1, 0);
for(int i = 0; i < n; i ++){  //creating i+1 bit gray code
int mirrorBoundary = res.size();
while(mirrorBoundary > 0){
mirrorBoundary --;
//add 1 to the most significant bit
int mirroredNum = res[mirrorBoundary];
mirroredNum +=  1<<(i);
res.push_back(mirroredNum);
}
}
return res;
}
};
``````