Bit Manipulation - Gray Code (Bit Manipulation)

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. Implement using the bit manipulation formula.

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

Input: n = 3 → Output: [0,1,3,2,6,7,5,4]

The i-th value in the Gray code sequence is computed by: gray(i) = i XOR (i >> 1). This formula ensures adjacent numbers differ by exactly one bit.

For i from 0 to 2^n - 1:
Compute i ^ (i >> 1) to get the Gray code value at position i.
Add to result list.
This O(1) per element formula works because: rightward shift aligns the highest differing bit between i and i-1.

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