Gray Code - Leetcode Solution

The Gray Code problem on LeetCode asks us to generate a sequence of n-bit Gray codes. A Gray code is a sequence of binary numbers where each successive number differs in only one bit.

For example, the 3-bit Gray code sequence is:

000 001 011 010 110 111 101 100

To generate the Gray code sequence for n bits, we can use the following recursive formula:

1. Base case: n = 0, the Gray code sequence contains only 0.
2. Recursive case: a. Generate the Gray code sequence for n-1 bits. b. Reverse the Gray code sequence generated in step 2a. c. Add '1' as the most significant bit to all the numbers in the reversed sequence. d. Combine the sequences generated in step 2a and step 2c to get the Gray code sequence for n bits.

Let's implement the above algorithm in Python:

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        
        prev_gray_code = self.grayCode(n-1)
        reversed_gray_code = prev_gray_code[::-1]
        new_gray_code = [2**(n-1) + code for code in reversed_gray_code]
        
        return prev_gray_code + new_gray_code

In the above code, we first handle the base case where n is zero. We return a list containing only 0.

For the recursive case, we generate the Gray code sequence for n-1 bits using the same recursive function. We then reverse this sequence and add 2^(n-1) to all the numbers in the reversed sequence, where ^ is the exponentiation operator. This gives us a new sequence of n-bit Gray codes. Finally, we combine the sequences generated in the previous step and the current step to get the full Gray code sequence for n bits.

The time complexity of this algorithm is O(2^n), since we generate 2^n numbers in the Gray code sequence. The space complexity is also O(2^n), since we need to store the entire Gray code sequence.

1