Gray Code

May 6, 2023

Explanation

This problem is tricky. The key is to find the pattern.

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

For example, when n = 3, we can get the result based on n = 2.

00, 01, 11, 10 -> 100, 101, 111, 110 (add 2 ** 2) -> 110, 111, 101, 100 (reverse)

Now, the answer for n = 3 is the answer for n = 2 and its reverse plus 2 ** 2.

Code

from typing import List

def gray_code(i: int) -> List[int]:
    if i == 1:
        return [0, 1]
    return gray_code(i - 1) + [2 ** (i - 1) + x for x in reversed(gray_code(i - 1))]

n = int(input())
print(*[bin(e)[2::].zfill(n) for e in gray_code(n)], sep="\n")