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)\).