Gray Code

An n-bit Gray code sequence is a sequence of 2^n integers where every consecutive pair of values differs by exactly one bit. Given n, return any valid n-bit Gray code sequence starting from 0.

Example 1

Input: n = 2 → Output: [0,1,3,2]

Example 2

Input: n = 1 → Output: [0,1]

Solution Approach

Use the reflection/induction approach: for n bits, the Gray code is built by taking the n-1 bit sequence, mirroring it, and prepending 0 to the original and 1 to the mirror. Equivalently, the i-th Gray code is i ^ (i >> 1).

For each integer i from 0 to 2^n - 1, compute i XOR (i >> 1).
This formula directly gives the Gray code at position i.
The resulting list automatically ensures adjacent entries differ by one bit.

Java

import java.util.*;

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

Time Complexity: O(2^n)
Space Complexity: O(1) extra (result list is the output)