Print the n-bit reflected Gray code: all 2ⁿ patterns of n bits, in the order used on Karnaugh maps, where each pattern differs from the one before in exactly one bit. It starts with all zeros.
Input
n (1 ≤ n ≤ 8).
Output
2ⁿ lines, one n-bit pattern each.
Examples
Example 1 · Input
2
Expected output
00 01 11 10
Example 2 · Input
3
Expected output
000 001 011 010 110 111 101 100
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The 1-bit Gray code is 0, 1.
Hint 2
The n-bit code is the (n-1)-bit code with 0 in front, followed by the (n-1)-bit code reversed with 1 in front.
Hint 3
Or use a formula: the k-th code is k ^ (k >> 1), written with n binary digits.
Solution
Show one correct solution (try it yourself first)
n = int(input())
for k in range(2 ** n):
print(format(k ^ (k >> 1), "0" + str(n) + "b"))