Gray Code

An n-bit gray code sequence is a sequence of 2^n integers where:

• Every integer is in the inclusive range [0, 2^n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

For example:

Input: n = 2 Output: [0,1,3,2] Explanation: The binary representation of [0,1,3,2] is [00,01,11,10].

• 00 and 01 differ by one bit
• 01 and 11 differ by one bit
• 11 and 10 differ by one bit
• 10 and 00 differ by one bit

[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].

• 00 and 10 differ by one bit
• 10 and 11 differ by one bit
• 11 and 01 differ by one bit
• 01 and 00 differ by one bit

Input: n = 1 Output: [0,1]

def grayCode(n):
    """
    Generates a Gray Code sequence of length 2^n for a given integer n.
    
    The Gray Code sequence satisfies the following properties:
    1.  Every integer is in the inclusive range [0, 2^n - 1].
    2.  The first integer is 0.
    3.  An integer appears no more than once in the sequence.
    4.  The binary representation of every pair of adjacent integers differs by exactly one bit.
    5.  The binary representation of the first and last integers differs by exactly one bit.
    
    :param n: The integer representing the number of bits.
    :return: A list of integers representing the Gray Code sequence.
    """
    if n == 0:
        return [0]

    # Recursive call for n-1
    prev_gray_code = grayCode(n - 1)

    # Generate the new gray code by reflecting the previous one and adding 2**(n-1)
    new_gray_code = prev_gray_code + [x + (1 << (n - 1)) for x in reversed(prev_gray_code)]

    return new_gray_code

# Example usage:
n = 2
result = grayCode(n)
print(result)

# Naive approach - not efficient
# Generate all possible numbers from 0 to 2^n - 1, and check if they satisfy Gray code properties
# This involves checking Hamming distance between adjacent numbers, which is inefficient

# Optimized approach - using reflection
# Generate Gray code for n-1, reflect it, and add 2^(n-1) to the reflected sequence

# Time complexity: O(2^n) - we generate a sequence of length 2^n
# Space complexity: O(2^n) - to store the gray code sequence

Naive Approach

The naive approach would involve generating all possible numbers from 0 to $2^n - 1$, and then checking if a sequence can be formed that satisfies the Gray code properties. This means checking the Hamming distance between adjacent numbers to ensure they differ by only one bit. This approach is highly inefficient because it involves generating all possible permutations and checking each one.

Optimal Solution

The optimal solution uses a reflection technique based on the following recursive definition:

1. The Gray code for $n=0$ is [0].
2. For $n > 0$, generate the Gray code for $n-1$, reflect it, and add $2^{n-1}$ to the reflected sequence.

This method directly constructs the Gray code sequence without generating and testing all possible permutations, making it much more efficient.

Code Implementation

def grayCode(n):
    if n == 0:
        return [0]

    prev_gray_code = grayCode(n - 1)
    new_gray_code = prev_gray_code + [x + (1 << (n - 1)) for x in reversed(prev_gray_code)]

    return new_gray_code

Big(O) Run-time Analysis

The time complexity of the optimal solution is $O(2^n)$. The algorithm generates a Gray code sequence of length $2^n$. The recursive calls build the sequence by reflecting the previous Gray code and adding $2^{n-1}$ to each element in the reversed sequence. The loop that adds $2^{n-1}$ iterates $2^{n-1}$ times, and since this process is repeated for each $n$, the overall time complexity is $O(2^n)$.

Big(O) Space Usage Analysis

The space complexity of the optimal solution is $O(2^n)$. This is because the algorithm stores the Gray code sequence in a list, which contains $2^n$ integers. The recursive calls also consume stack space, but the depth of the recursion is $n$, so the stack space is $O(n)$. However, since $2^n$ grows much faster than $n$, the dominant factor in space complexity is $O(2^n)$.

Edge Cases

1. $n = 0$: The function should return [0].
2. $n = 1$: The function should return [0, 1].
3. Large $n$: For larger values of $n$, the sequence can become very long, but the algorithm should still produce the correct Gray code sequence. For example, if $n = 16$, the sequence will have $2^{16} = 65536$ elements.