Domain 2MediumCORE

Gray Code

We need to generate a sequence of integers representing Gray codes for n bits. The output must be an array where the first element is always 0. Crucially, every adjacent pair in this list (including wrapping around if considered cyclic) differs by exactly one bit position. Given constraints $1 le n le 16$, we need to handle up to $2^{16}$ elements ($approx 65k$), which fits comfortably within standard memory limits but requires an efficient generation strategy rather than brute-force permutation checking.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking

89. Gray Code

Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 0
Acceptance rate: 50.7%


Problem Breakdown

We need to generate a sequence of integers representing Gray codes for n bits. The output must be an array where the first element is always 0. Crucially, every adjacent pair in this list (including wrapping around if considered cyclic) differs by exactly one bit position. Given constraints 1≤n≤161 \le n \le 16, we need to handle up to 2162^{16} elements (≈65k\approx 65k), which fits comfortably within standard memory limits but requires an efficient generation strategy rather than brute-force permutation checking.

Intuition

A naive approach would be to generate all possible binary numbers of length n and try permutations until we find one satisfying the adjacency constraint. This is infeasible because there are (2n)!(2^n)! potential orderings, making it exponential or factorial time complexity relative to NN.

Instead, observe small cases:

  • For n=1n=1, sequence is [0, 1] (binary 0, 1).
  • For n=2n=2, we can extend the previous list. If we take our current valid Gray code for kk bits and prefix a 0 to all elements, then reverse that list and prefix a 1 to each element, we maintain the single-bit difference property. The reversal ensures that when traversing back from high values to low values in the new bit dimension, only the MSB flips while lower bits traverse their previous sequence backwards (which is valid since they differ by one bit). This recursive reflection pattern allows us to construct the solution iteratively without searching or checking constraints at every step.

Approach

We will use an iterative construction based on the reflection property derived in intuition:

  1. Initialize a list with [0].
  2. Iterate from bit = 1 up to nn. In each iteration, we double the size of our current sequence (since adding one bit doubles the number of states).
  3. For every element currently in the list, append it unchanged (effectively prefixing a 0).
  4. Then iterate through the reversed version of the current list and for each element, add the value with the new MSB set (element | bit), appending these to our result.
  5. This ensures we traverse all combinations where only one bit changes between steps.

Complexity Analysis

  • Time: O(2n)O(2^n). We perform a constant amount of work for each element in the output list, and there are exactly 2n2^n elements required by definition. The total number of append operations across all iterations equals the final sequence length.
  • Space: O(2n)O(2^n) to store the result array itself. If implemented recursively without iteration optimization, we would add an additional stack space proportional to n, but our iterative approach keeps auxiliary space minimal relative to the output size.

Solution

def grayCode(n: int) -> list[int]:
    # Start with base case for 0 bits (conceptually), represented as [0]
    res = [0]
    
    # Iterate through each bit position from 1 up to n
    current_bit_value = 1
    
    while len(res) < (1 << n):
        # To maintain Gray code property when adding a new MSB:
        # We take the existing sequence, keep it as is (MSB=0), 
        # then reverse and add with MSB=1.
        
        # Create reversed copy of current list to append high-bit values in correct order
        for x in res[::-1]:
            res.append(x | current_bit_value)
            
        # Shift the bit mask left by 1 (equivalent to doubling value: 2^k -> 2^(k+1))
        current_bit_value <<= 1
        
    return res

# Example usage matching constraints
print(grayCode(2)) 

Edge Cases Handled

  • Minimum n (n=1n=1): The loop runs once, doubling [0] to [0, 1], which satisfies the constraint.
  • Maximum n (n=16n=16): Generates 2162^{16} integers; Python handles large lists and integer values without overflow issues within this range (values fit in standard machine words).
  • Starting Value: The algorithm initializes with [0], guaranteeing the sequence always starts at 0 as required.