1. Problem Statement (Simple Explanation)
You need to generate an n-bit Gray code sequence: a list of 2n integers such that:
Every integer is in [0, 2n - 1].
The first integer is 0.
No integer appears more than once.
The binary representations of any two adjacent integers differ by exactly one bit.
The first and last integers also differ by exactly one bit (cyclic Gray code).
You can return any valid sequence.
1 <= n <= 16.
2. Examples
Example 1:
Input: n = 2
One valid output: [0, 1, 3, 2]
Binary:
0 → 00
1 → 01
3 → 11
2 → 10
Differences:
00 → 01 (one bit)
01 → 11 (one bit)
11 → 10 (one bit)
10 → 00 (one bit, cyclic)
Another valid sequence: [0, 2, 3, 1].
Example 2:
Input: n = 1
Gray code sequence is just: [0, 1]
Binary:
0 → 0
1 → 1 (one bit difference, and cyclic with 0).
3. Approach 1 – Direct Formula: g(i) = i ^ (i >> 1) (O(2^n))
There is a well-known formula for generating n-bit Gray codes:
The i-th Gray code is
g(i) = i ^ (i >> 1)
(where ^ is bitwise XOR, >> is right shift)
Properties:
For i from 0 to 2n - 1, g(i) gives a Gray code sequence.
Adjacent g(i) and g(i+1) differ by exactly 1 bit.
g(0) = 0.
This is the simplest and most efficient way to generate an n-bit Gray code.
Pseudo-code:
Complexity:
Number of codes: 2n (required).
Time: O(2n).
Space: O(2n) for the result.
4. Approach 2 – Recursive Reflect-and-Prefix (Conceptual)
For understanding:
1-bit Gray code: [0, 1]
To build (n+1)-bit Gray code from n-bit:
Take n-bit Gray sequence G.
New sequence:
Prefix 0 to each code in G (in order).
Then prefix 1 to each code in G (in reverse order).
E.g., from n=2 to n=3:
2-bit: [00, 01, 11, 10] → [0,1,3,2]
3-bit:
0 prefix: [000, 001, 011, 010] → [0,1,3,2]
1 prefix on reverse: [110, 111, 101, 100] → [6,7,5,4]
Combined: [0,1,3,2,6,7,5,4]
This construction also ensures Gray code properties.
In practice, formula method is simpler.
5. Java code
6. C code
7. C++ code
8. Python code
9. JavaScript code
Comments
Post a Comment