Code Implementation

class Solution:
    def grayCode(self, n: int) -> list[int]:
        result = []
        for i in range(1 << n):
            result.append(i ^ (i >> 1))
        return result
      

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        int size = 1 << n;
        for (int i = 0; i < size; ++i) {
            result.push_back(i ^ (i >> 1));
        }
        return result;
    }
};
      

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

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

Problem Description

You are given a non-negative integer n representing the total number of bits in a binary code. Your task is to generate a sequence of integers (the Gray code sequence) such that:

• The sequence contains all numbers from 0 to 2^n - 1 exactly once.
• Each number in the sequence differs from the previous one by exactly one bit in its binary representation.
• The sequence starts with 0.

The problem guarantees that at least one valid solution exists for any n. The output should be a list of integers in the required order.

Thought Process

The first step is to understand what a Gray code sequence is. In a Gray code, two consecutive numbers differ by only one bit. For example, for n = 2, the Gray code sequence is [0, 1, 3, 2] (in binary: 00, 01, 11, 10).

At first glance, one might consider generating all binary numbers of n bits and checking if each pair differs by one bit, but this is inefficient. The challenge is to find a systematic and efficient way to generate such a sequence for any n.

The key insight is that Gray codes can be generated directly using a mathematical formula or by reflecting and prefixing the sequence as n increases. This allows us to avoid brute-force checking and use a simple loop or recursion.

Solution Approach

There are several ways to generate a Gray code sequence, but the most efficient and elegant uses the binary formula: for any integer i, its Gray code is i ^ (i >> 1). Here’s why and how this works:

1. Iterate from 0 to 2ⁿ - 1: These represent all possible combinations of n bits.
2. Convert each number to Gray code: For each i, compute i ^ (i >> 1). This flips only one bit at a time as i increases, ensuring the Gray code property.
3. Store the result: Collect all the Gray codes in a list and return them.

This method is efficient, simple, and guarantees the sequence starts at 0 and covers all numbers exactly once.

Example Walkthrough

Let’s walk through the process for n = 2:

1. i = 0: 0 in binary is 00. 0 ^ (0 >> 1) = 0 ^ 0 = 0
2. i = 1: 1 in binary is 01. 1 ^ (1 >> 1) = 1 ^ 0 = 1
3. i = 2: 2 in binary is 10. 2 ^ (2 >> 1) = 2 ^ 1 = 3
4. i = 3: 3 in binary is 11. 3 ^ (3 >> 1) = 3 ^ 1 = 2

The resulting sequence is [0, 1, 3, 2], which in binary is 00, 01, 11, 10. Each pair differs by exactly one bit, meeting the Gray code requirement.

Time and Space Complexity

• Brute-force approach: Generating all permutations and checking the one-bit difference between consecutive elements is factorial time (O((2^n)!)), which is infeasible for even moderate n.
• Optimized approach (using the formula): The loop runs from 0 to 2^n - 1 (O(2^n)). Each computation and insertion is O(1), so total time is O(2^n). Space complexity is also O(2^n) to store the result.

The optimized approach is efficient and suitable for the problem constraints.

Summary

The Gray code problem asks for a sequence of all n-bit numbers where each consecutive number differs by only one bit. By using the formula i ^ (i >> 1) for each number from 0 to 2^n - 1, we can generate the sequence efficiently, avoiding brute-force search. This approach is both elegant and optimal, leveraging bitwise operations to produce the desired result.