89. Gray Code
An n-bit Gray code is an ordering of all 2^n n-bit values in which every pair of consecutive entries differs in exactly one bit — and the last entry also differs from the first in exactly one bit, so the sequence forms a closed loop.
Many orderings have this property, so to make the answer unique you must produce the classic reflected sequence. It is built like this: the 1-bit sequence is 0, 1. To grow from n−1 bits to n bits, keep the current sequence as the first half, then append the same sequence in reverse order with the new highest bit set on every appended entry.
Given the integer n, return the n-bit reflected Gray code sequence as decimal integers. It always begins at 0.
Example 1:
Input: n = 2
Output: [0, 1, 3, 2]
Explanation: In binary the sequence reads 00, 01, 11, 10 — each step flips one bit, and 10 → 00 closes the loop with one flip. It is the 1-bit sequence (0, 1) followed by its reversal (1, 0) with the 2s bit set (3, 2).
Example 2:
Input: n = 3
Output: [0, 1, 3, 2, 6, 7, 5, 4]
Explanation: The first half is the 2-bit sequence 0, 1, 3, 2; the second half is that run reversed (2, 3, 1, 0) with the 4s bit set: 6, 7, 5, 4.
Constraints:
- 1 ≤ n ≤ 14
Hints:
Build it exactly as the definition says. If you already hold the (n−1)-bit sequence in a list, walking that list backward while OR-ing in the new top bit produces the entire second half — the reversal is what makes the seam between the halves a single-bit flip.
There is also a one-line closed form: entry k of the reflected sequence is k XOR (k >> 1). Sanity-check it against n = 2: k = 0..3 gives 0, 1, 3, 2.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2
Expected output: [0, 1, 3, 2]