Gray Code
Problem
An n-bit Gray code sequence is a sequence of 2n integers where every value is in [0, 2n-1], the first integer is 0, every integer appears exactly once, and consecutive integers (including the wraparound from last to first) differ by exactly one bit. Return any valid n-bit Gray code sequence.
n = 3[0, 1, 3, 2, 6, 7, 5, 4]def gray_code(n):
out = []
for i in range(1 << n):
out.append(i ^ (i >> 1))
return outfunction grayCode(n) {
const out = [];
for (let i = 0; i < (1 << n); i++) {
out.push(i ^ (i >> 1));
}
return out;
}class Solution {
public List<Integer> grayCode(int n) {
List<Integer> out = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
out.add(i ^ (i >> 1));
}
return out;
}
}vector<int> grayCode(int n) {
vector<int> out;
for (int i = 0; i < (1 << n); i++) {
out.push_back(i ^ (i >> 1));
}
return out;
}Explanation
A Gray code lists all numbers from 0 to 2^n - 1 so that any two neighbors differ by exactly one bit. There is a famous one-line formula that produces such a sequence: g(i) = i ^ (i >> 1).
We simply loop i from 0 upward and emit i ^ (i >> 1) each time. No backtracking or bookkeeping is required because the formula already guarantees the one-bit property.
Why it works intuitively: XOR-ing a number with itself shifted right by one bit blends each bit with its neighbor. As i increases by one, only a small, controlled change ripples through, so consecutive outputs end up differing in a single bit.
Example: n = 3. For i = 0,1,2,3,... we get 0, 1, 3, 2, 6, 7, 5, 4. In binary that is 000, 001, 011, 010, 110, 111, 101, 100, and each adjacent pair flips just one bit.
Each value is one shift and one XOR, so generating all 2^n codes takes time proportional to the sequence length.