Gray Code

89.Gray Code

Recursion

Bit Manipulation

Math

Problem Statement:

The gray code is a sequence of numbers where each number differs by only one bit from its predecessor. Given an integer n, generate all possible n-bit gray code sequences in any order.

Example:

Input:

n = 2

→

Output:

[0,1,3,2]

Algorithm:

1. Use recursive approach to build sequence
2. Generate n-1 bit codes first
3. Reflect and prefix with 1 for n bits
4. Base case returns [0] for n=0

Complexity:

Time: O(2^n) | Space: O(2^n)

Java Solution:

public List<Integer> grayCode(int n) {
    if(n == 0) {  // Base case: return [0]
        List<Integer> result = new ArrayList<Integer>();
        result.add(0);
        return result;
    }
    
    List<Integer> result = grayCode(n - 1);  // Get n-1 bit codes
    int prefix = 1 << (n-1);  // Calculate prefix for reflection
    
    for (int i = result.size() - 1; i >= 0; i--) {
        result.add(prefix + result.get(i));  // Add reflected values
    }
    
    return result;
}

Python Solution:

def grayCode(self, n: int) -> List[int]:
    if n == 0:
        return [0]
    
    result = self.grayCode(n - 1)  # Get n-1 bit codes
    prefix = 1 << (n - 1)  # Calculate prefix
    
    for i in range(len(result) - 1, -1, -1):
        result.append(prefix + result[i])  # Add reflected values
        
    return result

C++ Solution:

class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) {
            return {0};
        }
        
        vector<int> result = grayCode(n - 1);  // Get n-1 bit codes
        int prefix = 1 << (n - 1);  // Calculate prefix
        
        for(int i = result.size() - 1; i >= 0; i--) {
            result.push_back(prefix + result[i]);  // Add reflected values
        }
        
        return result;
    }
};