[CSES] Gray Code

2022-03-15

2 minute read

Algorithm

cses

Gray Code

Task:

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 \le n \le 16$

Example

Input:
2

Output:

Solutions:

Intuition:

If you write down the sequence of Gray Code from $n=1$ to $n=3$, I think it can help to give an intuition about its pattern.

$n=1: 0 \; 1$
$n=2: 00 \; 01 \; 11 \; 10$
$n=3: 000 \; 001 \; 011 \; 010 \; 110 \; 111 \; 101 \; 100$

For each of sequence, if we divide it into 2 halves and remove the MSB ( most significant bit), the first half will be look like the previous sequence (n-1), meanwhile the remaining half is formed in reversed pattern. The MSB is 0 and 1 in turn. \[ \begin{array}{|c|c|l|} \hline \textbf{n} & \textbf{Sequence} & \textbf{Explanation} \\ \hline \ 1 & 0 \; 1 & \text{base} \\ \hline \ 2 & 00 \; 01 \; | \; 11 \; 10 & \text{0 -> to the previous sequence ( 0 1 ) : } \textcolor{red}{0}0 \; \textcolor{red}{0}1 \\ & & \text{1 -> to the previous reversed sequence (1 0) : } \textcolor{red}{1}1 \; \textcolor{red}{1}0\\ \hline \ 3 & 000 \; 001 \; 011 \; 010 \; | \; 110 \; 111 \; 101 \; 100 & 0 -> 000 \; 001 \; 011 \; 010 \\ & & 1 -> 110 \; 111 \; 101 \; 100 \\ \hline \end{array} \] This strategy can be implemented by using recursion, or merely loop.

Implementation:

 1def grayCode(n: int):
 2    prev = ["0","1"]
 3    for i in range(1,n):
 4        fir_half=["0"+i for i in prev]
 5        sec_half=["1"+i for i in prev[::-1]]
 6        prev=fir_half+sec_half
 7    for i in prev:
 8        print(i)
 9
10n=int(input())
11grayCode(n)
12

Time complexity: O(N).

Space complexity: O(N).

It appears that Gray code can be solve with less runtime as well as memory usage. Based on an orderly formula, we can convert consecutive Binary code to valid Gray code sequence.

The MSB of Gray Code is always equivalent to the respective Binary.
The next bit in Gray Code can be formed by doing XOR the bit of current index with previous index bit in Binary code.

Because It's the XOR operation with 2 successive bits, shifting is a good choice for lean implementation. In order to hold the same MSB, right shift should be chosen.
For ex:
The 11th Gray code number is achieved by doing a transformation from Binary 11 to Graycode.

11 in Binary: 1011
Right shift: $1011>>1 = 0101$
XOR: $1011 \oplus 0101$ = 1110

11th GrayCode number is $1110$

Implementation:

1    import math
2    def g(n):
3        return n^(n>>1)
4    def grayCode(n):
5        for i in range(2**n):
6            res=bin(g(i))[2:]
7            print((n-len(res))*"0"+res)
8    grayCode(int(input()))
9

Analysis:

Time complexity: O(N).

Space complexity: O(1).