mediumBit ManipulationPure DSA~20 min
Generate an N-Bit Gray Code Sequence
Produce a sequence of all 2^n n-bit numbers where consecutive entries (and the first and last) differ in exactly one bit.
Problem
Given an integer n, return any valid n-bit Gray code sequence: a permutation of 0..2^n - 1 starting at 0 where every pair of adjacent integers (including the last and first) differs in exactly one bit.
Input
A single integer n.
Output
A list of 2^n integers forming a Gray code sequence.
Constraints
- 1 <= n <= 16
- The sequence must start at 0.
- Adjacent values differ in exactly one bit.
Examples
Example 1
Input
n = 2
Output
[0,1,3,2]
00 -> 01 -> 11 -> 10, each a single-bit change.
Example 2
Input
n = 1
Output
[0,1]
0 and 1 differ in one bit.