Gray Code
Medium · Bit Manipulation · Math · Backtracking · Bit Manipulation
Problem
An n-bit Gray code is a sequence of 2^n integers such that:
- every integer lies in [0, 2^n - 1] and appears exactly once,
- the first integer is 0,
- any two consecutive integers differ in exactly one bit, and
- the last integer also differs from the first in exactly one bit.
Given n, return any valid n-bit Gray code sequence. Several sequences are valid for most n; any of them is accepted.
Examples
Input: n = 1 Output: [0,1]
The only sequence is 0, 1.
Input: n = 2 Output: [0,1,3,2]
00, 01, 11, 10: each step changes one bit, and 10 is one bit from 00. [0,2,3,1] is also accepted.
Input: n = 3 Output: [0,1,3,2,6,7,5,4]
Every neighbor pair differs in one bit, and 4 (100) is one bit from 0. Other valid orders are also accepted.
Constraints
- 1 <= n <= 16
Approaches
- Backtracking over one-bit moves — time O(n · 2^n) here; exponential for a general search, space O(2^n)
Follow-up
To go back from a Gray code g to its position i, undo the XOR: i is the XOR of g >> k over all k, which can be computed by i = g; while g: g >>= 1; i ^= g. And a sequence that must start at some other value s is simply every code XORed with s.
Related problems
Start free on Cariara · Coding problems · System design studio
