Gray Code (Bit Manipulation)

Share

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.

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

Solution Approach

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.
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