Solution Explanation: Gray Code Generation

This problem asks to generate a Gray code sequence of length 2n, where n is the input integer. A Gray code is a binary numeral system where two successive values differ in only one bit.

Approach: Direct Gray Code Conversion

The most efficient approach leverages the direct mathematical relationship between a binary number and its Gray code equivalent. The Gray code G of a binary number B can be calculated using the formula:

G = B ^ (B >> 1)

where ^ represents the bitwise XOR operation and >> is the right bit shift. This formula efficiently converts a binary number to its Gray code equivalent.

Algorithm

1. Iterate: Loop through numbers from 0 to 2n - 1.
2. Convert to Gray Code: For each number, apply the formula G = B ^ (B >> 1) to obtain its Gray code.
3. Store: Add the calculated Gray code to the result list.
4. Return: Return the list containing the generated Gray code sequence.

Time and Space Complexity

• Time Complexity: O(2n). The algorithm iterates through 2n numbers, and the Gray code conversion for each number is O(1) (constant time).
• Space Complexity: O(2n). The resulting Gray code sequence is stored in a list of size 2n. If we ignore the space for the output list, the space complexity is O(1).

Code Implementations

The following code implementations demonstrate the solution in various programming languages:

Python

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]

Java

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

C++

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

Go

func grayCode(n int) []int {
	result := make([]int, 1<<n)
	for i := 0; i < 1<<n; i++ {
		result[i] = i ^ (i >> 1)
	}
	return result
}

JavaScript

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

All these implementations follow the same core algorithm, providing a concise and efficient solution to generate the Gray code sequence. They differ only in syntax and specific language features.