Generate the Full n-bit Gray Code Sequence

Given an integer n, generate the n-bit binary-reflected Gray code sequence: the 2^n binary strings of length n such that every pair of consecutive strings (including the pair formed by the last and the first, wrapping around) differs in exactly one bit, starting from "000...0". Print each code as an n-character binary string, one per line, in generation order.

Input: A single line containing the integer n. Output: 2^n lines, each an n-character binary string: the successive Gray codes in order.

1 <= n <= 16

The 'reflect and prefix' recursive construction and the direct i XOR (i>>1) formula produce the EXACT SAME sequence - recognizing that a seemingly recursive construction has an equivalent O(1)-per-element closed form is a valuable pattern-recognition skill.

Generate the sequence of n-bit binary numbers where every consecutive pair (including wrapping from last back to first) differs in exactly one bit. Brute force: Build the sequence recursively using the classic 'reflect and prefix' construction (take the (n-1)-bit sequence, prefix a 0 to each entry, then prefix a 1 to the REVERSED (n-1)-bit sequence) - this works correctly and is the traditional way to explain Gray codes, but requires building up smaller sequences first. Optimised: The direct formula i XOR (i >> 1) computes EACH Gray code independently, with no need to build up from smaller sequences recursively - applying it in a simple loop from i=0 to 2^n-1 produces the entire standard sequence directly, in the exact same order the recursive reflect-and-prefix construction would produce.

1. Use the direct formula: the i-th Gray code (0-indexed) equals i XOR (i >> 1). 2. Apply this formula for i = 0 through 2^n - 1, in order, to directly produce the entire sequence with no recursion needed. 3. Left-pad each result with zeros so every code has exactly n characters, even for small numeric values.

Time: O(2^n * n) - generating each of the 2^n codes takes O(n) to format as an n-character binary string. Space: O(n) per generated code (or O(2^n * n) if all codes are stored at once).

n = 1 produces just "0" then "1"; n = 16 produces 65536 codes, so the generation must be done with a formula rather than an exponential-time recursive reflection.

Be ready to explain WHY i XOR (i >> 1) guarantees consecutive codes differ by exactly one bit - this isn't obvious at a glance, and being able to justify it (rather than just reciting the formula) is what separates surface-level knowledge from genuine understanding.