# Gray Code Solution

23 November 2021

Statement

( The original statement can be found here )
A Gray code is a list of all $$2^n$$ bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length $$n$$.

Input
The only input line has an integer $$n$$.

Output
Print $$2^n$$ lines that describe the Gray code. You can print any valid solution.

Constraints
1 ≤ n ≤ $$16$$
Time limit : 1.00s
Memory limit : 512MB

Example

Input :
2

Output :
00
01
11
10

Solution

How can we generate all bit strings of length $$N$$ where two successive strings differ in exactly one bit?

If you read the statement carefully, you will notice a little hint. We are asked to "list all $$2^n$$ bit strings", which means that there is a way of reordering all the possible bit strings that satisfies our original requirements. It also indicates that generating this list might require doubling its size $$N$$ times (and that is indeed part of the solution).

One possible solution to this problem is to start with a list of two elements {"0", "1"} . The idea is to duplicate this list and append it to the original list in reverse order, so that we get {"0", "1", "1", "0"} . The final step is to append a "0" to the first half and a "1" to the second half of the resulting list. We only need to repeat this process $$N$$ times. The trick is to understand that by reversing and appending a copy of the list to the original, the middle elements are the same, differing only by the newly added bit.

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

int main() {
int n;
cin >> n;
vector<string> gray_code;
gray_code.push_back("");
for (int i = 0; i < n; i++) {
int size = gray_code.size();
for (int j = size - 1; j >= 0; j--) {
gray_code.push_back(gray_code[j]);
}
size *= 2;
for (int j = 0; j < size; j++) {
if (j < gray_code.size() / 2) {
gray_code[j] += "0";
} else {
gray_code[j] += "1";
}
}
}
for (int i = 0; i < gray_code.size(); i++) {
cout << gray_code[i] << endl;
}
}


Since we have to generate every possible string and store it in a list, the time and space complexities are $$O(2^n)$$.