Gray Code Explained

Problem Statement

Given a non-negative integer n representing the number of bits, generate a Gray code sequence of length 2^n. A Gray code sequence is a sequence of integers where each consecutive pair differs by exactly one bit, starting with 0. This problem tests your understanding of Gray code properties, where each number can be computed as i ^ (i >> 1), ensuring the one-bit difference.

Example

Input: n = 2

Output: [0,1,3,2]

Explanation: In binary: 00, 01, 11, 10. Each pair differs by exactly one bit (00^01, 01^11, 11^10).

Code

import java.util.ArrayList;
import java.util.List;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.grayCode(2)); // [0, 1, 3, 2]
    }
}
            

def gray_code(n):
    result = []
    for i in range(1 << n):
        result.append(i ^ (i >> 1))
    return result

# Example usage
print(gray_code(2))  # [0, 1, 3, 2]
            

function grayCode(n) {
    const result = [];
    for (let i = 0; i < (1 << n); i++) {
        result.push(i ^ (i >> 1));
    }
    return result;
}

// Example usage
console.log(grayCode(2)); // [0, 1, 3, 2]
            

Explanation

• Generate integers from 0 to 2^n - 1 using a loop.
• For each integer i, compute its Gray code as i ^ (i >> 1).
• This formula ensures that each number differs from the previous by exactly one bit.
• Add the computed Gray code to the result list.
• Return the complete sequence.

Note