89. Gray Code

MediumBit ManipulationMathBacktracking

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You need to generate a Gray code sequence of length 2^n for a given integer n.

A Gray code sequence is a special ordering of binary numbers with these properties:

Range: All integers in the sequence must be between 0 and 2^n - 1 (inclusive)
Starting point: The sequence must begin with 0
Uniqueness: Each integer appears exactly once in the sequence
Adjacent difference: Any two consecutive numbers in the sequence must differ by exactly one bit in their binary representation
Circular property: The first and last numbers in the sequence must also differ by exactly one bit

For example, when n = 2, one valid Gray code sequence is [0, 1, 3, 2]:

0 (binary: 00) and 1 (binary: 01) differ by one bit
1 (binary: 01) and 3 (binary: 11) differ by one bit
3 (binary: 11) and 2 (binary: 10) differ by one bit
2 (binary: 10) and 0 (binary: 00) differ by one bit

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Each Gray code value equals i XOR (i >> 1), a closed-form bit identity over the index.

Open in Flowchart

Show step-by-step reasoning

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

No: The Gray code problem doesn't involve nodes and edges in a graph structure. We're generating a sequence of integers with specific bit-difference properties.

Need to solve for kth smallest/largest?

No: We're not looking for the kth smallest or largest element. We need to generate a complete sequence of 2^n integers.

Involves Linked Lists?

No: The problem doesn't involve linked list data structures. We're working with a sequence of integers.

Does the problem have small constraints?

Yes: The constraint n is typically small (often n ≤ 16 in practice), which means we're generating at most 2^16 = 65536 numbers. This is manageable for exhaustive exploration approaches.

Brute force / Backtracking?

Yes: Given the small constraints and the need to generate all valid sequences where each number appears exactly once and adjacent numbers differ by one bit, backtracking is a natural fit. We can build the sequence step by step, backtracking when we can't find a valid next number that hasn't been used and differs by exactly one bit.

Conclusion: The flowchart suggests using a backtracking approach for generating the Gray code sequence. While the provided solution uses a mathematical formula (i ^ (i >> 1)), backtracking would also work by:

Starting with 0
At each step, trying all numbers that differ by exactly one bit from the current number
Backtracking if we hit a dead end (no valid unused numbers available)
Ensuring the final number differs by one bit from 0 to complete the cycle

Intuition

While backtracking could solve this problem by exhaustively trying different sequences, there's a beautiful mathematical pattern hidden in Gray codes that leads to a much more elegant solution.

Let's think about what makes Gray codes special: consecutive numbers differ by exactly one bit. If we look at the first few Gray code sequences:

For n=1: [0, 1] → [00, 01] in binary
For n=2: [0, 1, 3, 2] → [00, 01, 11, 10] in binary
For n=3: [0, 1, 3, 2, 6, 7, 5, 4] → [000, 001, 011, 010, 110, 111, 101, 100] in binary

Notice a pattern? When we go from binary number i to its Gray code representation, we're essentially looking at which bits change. The key insight is that a bit in the Gray code is 1 if and only if the corresponding bit in the binary number is different from the bit to its left.

This leads us to the formula: for any binary number, we can get its Gray code by XORing it with itself shifted right by one position. Why does this work?

When we compute i ^ (i >> 1):

The leftmost bit stays the same (since we're XORing with 0 from the shift)
Each other bit becomes the XOR of that bit and the bit to its left in the original number
This ensures that the Gray code bit is 1 only when there's a transition from 0 to 1 or 1 to 0 in the original binary representation

For example, binary 3 is 011:

3 >> 1 gives us 001
011 ^ 001 = 010 (which is 2 in decimal)
This is indeed the Gray code for position 3!

This mathematical relationship means we don't need backtracking at all - we can directly compute the Gray code for each position from 0 to 2^n - 1 using this simple formula, giving us an O(2^n) time solution with no recursion needed.

Pattern Learn more about Math and Backtracking patterns.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution uses the direct binary-to-Gray code conversion formula discovered through the mathematical relationship between binary numbers and their Gray code representations.

Core Algorithm: The implementation uses a list comprehension to generate all Gray codes from 0 to 2^n - 1:

[i ^ (i >> 1) for i in range(1 << n)]

Let's break down each component:

Range Generation: range(1 << n)
- 1 << n is equivalent to 2^n, using bit shifting for efficiency
- This generates all integers from 0 to 2^n - 1
Gray Code Conversion: i ^ (i >> 1)
- For each integer i, we apply the conversion formula
- i >> 1 shifts the binary representation of i one position to the right
- ^ performs XOR between i and its right-shifted version
- This preserves the highest bit and makes each other bit the XOR of adjacent bits in the original number

Why This Works: The formula ensures that consecutive Gray codes differ by exactly one bit. When we increment from i to i+1 in binary, the change pattern in the resulting Gray codes maintains the single-bit difference property.

Example Walkthrough for n=3:

i=0: 000 ^ 000 = 000 (Gray: 0)
i=1: 001 ^ 000 = 001 (Gray: 1)
i=2: 010 ^ 001 = 011 (Gray: 3)
i=3: 011 ^ 001 = 010 (Gray: 2)
i=4: 100 ^ 010 = 110 (Gray: 6)
i=5: 101 ^ 010 = 111 (Gray: 7)
i=6: 110 ^ 011 = 101 (Gray: 5)
i=7: 111 ^ 011 = 100 (Gray: 4)

Result: [0, 1, 3, 2, 6, 7, 5, 4] - a valid Gray code sequence!

Time and Space Complexity:

Time: O(2^n) - we generate exactly 2^n numbers
Space: O(2^n) - for storing the output list

This approach is optimal since we must generate all 2^n numbers, and each conversion takes O(1) time.

Example Walkthrough

Let's walk through generating a Gray code sequence for n = 2 using the formula i ^ (i >> 1).

Goal: Generate a sequence of length 2² = 4 containing all numbers from 0 to 3, where consecutive numbers differ by exactly one bit.

Step-by-step conversion:

For each position i from 0 to 3, we calculate its Gray code:

Position i = 0:

Binary: 00
Right shift by 1: 00 >> 1 = 00
XOR operation: 00 ^ 00 = 00
Gray code value: 0

Position i = 1:

Binary: 01
Right shift by 1: 01 >> 1 = 00
XOR operation: 01 ^ 00 = 01
Gray code value: 1

Position i = 2:

Binary: 10
Right shift by 1: 10 >> 1 = 01
XOR operation: 10 ^ 01 = 11
Gray code value: 3

Position i = 3:

Binary: 11
Right shift by 1: 11 >> 1 = 01
XOR operation: 11 ^ 01 = 10
Gray code value: 2

Final sequence: [0, 1, 3, 2]

Verification of Gray code properties:

0 (00) → 1 (01): differ in rightmost bit ✓
1 (01) → 3 (11): differ in leftmost bit ✓
3 (11) → 2 (10): differ in rightmost bit ✓
2 (10) → 0 (00): differ in leftmost bit ✓

Each consecutive pair differs by exactly one bit, including the wrap-around from last to first, confirming this is a valid Gray code sequence.

Solution Implementation

1class Solution:
2    def grayCode(self, n: int) -> List[int]:
3        """
4        Generate n-bit Gray code sequence.
5      
6        Gray code is a binary numeral system where two successive values
7        differ in only one bit.
8      
9        Args:
10            n: Number of bits for the Gray code sequence
11          
12        Returns:
13            List of integers representing the Gray code sequence
14        """
15        # Calculate the total number of Gray codes for n bits (2^n)
16        total_codes = 1 << n  # Equivalent to 2^n
17      
18        # Generate Gray code for each number from 0 to 2^n - 1
19        # Formula: Gray(i) = i XOR (i right-shifted by 1)
20        # This converts binary to Gray code directly
21        gray_code_sequence = [i ^ (i >> 1) for i in range(total_codes)]
22      
23        return gray_code_sequence
24

1class Solution {
2    /**
3     * Generates the n-bit Gray code sequence.
4     * Gray code is a binary numeral system where two successive values differ in only one bit.
5     * 
6     * @param n the number of bits for the Gray code
7     * @return a list containing the Gray code sequence in decimal representation
8     */
9    public List<Integer> grayCode(int n) {
10        // Initialize the result list to store Gray code values
11        List<Integer> result = new ArrayList<>();
12      
13        // Total number of Gray code values for n bits is 2^n
14        int totalNumbers = 1 << n;  // Equivalent to 2^n using bit shift
15      
16        // Generate each Gray code value using the formula: grayCode = i XOR (i >> 1)
17        for (int i = 0; i < totalNumbers; i++) {
18            // Convert binary number to Gray code using XOR operation
19            // The formula works by XORing each bit with the bit to its left
20            int grayCodeValue = i ^ (i >> 1);
21            result.add(grayCodeValue);
22        }
23      
24        return result;
25    }
26}
27

1class Solution {
2public:
3    vector<int> grayCode(int n) {
4        vector<int> result;
5      
6        // Generate all Gray code values for n bits
7        // Total number of Gray codes for n bits is 2^n
8        int totalCodes = 1 << n;  // Equivalent to 2^n
9      
10        for (int i = 0; i < totalCodes; ++i) {
11            // Convert binary number i to its corresponding Gray code
12            // Formula: Gray(i) = i XOR (i right-shifted by 1)
13            // This ensures adjacent codes differ by exactly one bit
14            int grayValue = i ^ (i >> 1);
15            result.push_back(grayValue);
16        }
17      
18        return result;
19    }
20};
21

1/**
2 * Generates the n-bit Gray code sequence.
3 * Gray code is a binary numeral system where two successive values differ in only one bit.
4 * 
5 * @param n - The number of bits for the Gray code
6 * @returns An array containing the Gray code sequence
7 */
8function grayCode(n: number): number[] {
9    const result: number[] = [];
10  
11    // Generate all numbers from 0 to 2^n - 1
12    // The total count of Gray codes for n bits is 2^n
13    const totalCodes = 1 << n; // Equivalent to 2^n
14  
15    for (let i = 0; i < totalCodes; i++) {
16        // Convert binary number to Gray code using the formula:
17        // Gray code = i XOR (i right-shifted by 1)
18        // This ensures adjacent codes differ by exactly one bit
19        const grayValue = i ^ (i >> 1);
20        result.push(grayValue);
21    }
22  
23    return result;
24}
25

Time and Space Complexity

The time complexity is O(2^n), where n is the input integer. This is because the list comprehension iterates through all integers from 0 to 2^n - 1 (since 1 << n equals 2^n), performing a constant-time XOR operation i ^ (i >> 1) for each integer.

The space complexity is O(1) if we exclude the space required for the output list. The algorithm only uses a loop variable i and performs bitwise operations without requiring any additional data structures. However, if we include the output list in the space complexity analysis, it would be O(2^n) since the returned list contains 2^n elements.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Searching for the Sequence Instead of Computing It

A common first attempt builds the sequence by search: from the last number, flip one bit at a time and append the first result that has not been used yet.

Pitfall Example:

def grayCode(self, n: int) -> List[int]:
    result = [0]
    used = {0}
  
    while len(result) < (1 << n):
        last = result[-1]
        for i in range(n):
            # Try flipping each bit
            candidate = last ^ (1 << i)
            if candidate not in used and candidate < (1 << n):
                result.append(candidate)
                used.add(candidate)
                break
    return result

Issue: This greedy search does produce a valid answer. Trying the lowest bit first reproduces exactly the sequence [i ^ (i >> 1) for i in range(1 << n)]. The cost is higher, though: each step tries up to n flips, so the run takes O(n · 2^n) time, and the used set adds O(2^n) extra memory. A search that picks candidates in a less regular order can also run into a dead end and need full backtracking.

Solution: Use the formula i ^ (i >> 1), which computes each entry in O(1) time with no bookkeeping.

2. Shifting in the Wrong Direction

The formula XORs i with i shifted to the right. Shifting left instead gives a different function.

Pitfall Example:

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

Issue: For n = 2 this returns [0, 3, 6, 5]. The values 6 and 5 fall outside the range 0 to 3, and 0 → 3 differs in two bits.

Note on precedence: In Python, Java, C++, and TypeScript, >> binds more tightly than ^, so i ^ i >> 1 already means i ^ (i >> 1). The parentheses are still worth writing because they make the intent clear to readers.

Solution: Shift right, and keep the parentheses for readability:

return [i ^ (i >> 1) for i in range(1 << n)]

3. Using Power Operator Instead of Bit Shift

While 2**n works correctly, it's less efficient than bit shifting for powers of 2.

Pitfall Example:

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

Issue: The ** operator is computationally more expensive than bit shifting, especially for larger values of n.

Solution: Use 1 << n for better performance:

return [i ^ (i >> 1) for i in range(1 << n)]

4. Attempting Recursive Mirror Construction

Some try to build Gray codes using the mirror reflection method recursively, which is correct but more complex and less efficient.

Pitfall Example:

def grayCode(self, n: int) -> List[int]:
    if n == 0:
        return [0]
  
    prev_gray = self.grayCode(n - 1)
    result = prev_gray[:]
  
    for i in range(len(prev_gray) - 1, -1, -1):
        result.append(prev_gray[i] | (1 << (n - 1)))
  
    return result

Issue: While this works, it recurses n levels deep and copies a list at each level (1 + 2 + 4 + ... + 2^(n-1) copied elements in total), which is more work and more code than the direct formula.

Solution: The direct formula approach is simpler, more efficient, and avoids recursion overhead:

return [i ^ (i >> 1) for i in range(1 << n)]

5. Edge Case Handling for n=0

Not considering that when n=0, the sequence should be [0], not an empty list.

Pitfall Example:

def grayCode(self, n: int) -> List[int]:
    if n == 0:
        return []  # Wrong!
    return [i ^ (i >> 1) for i in range(1 << n)]

Issue: For n=0, there's still one valid Gray code: 0. The range should be [0, 2^0 - 1] = [0, 0].

Solution: The formula naturally handles this case correctly:

return [i ^ (i >> 1) for i in range(1 << n)]  # Works for n=0 too!

When n=0, range(1 << 0) = range(1) = [0], and 0 ^ (0 >> 1) = 0.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know

89. Gray Code

Problem Description

How We Pick the Algorithm

Why Math / Bit Manipulation?

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Searching for the Sequence Instead of Computing It

2. Shifting in the Wrong Direction

3. Using Power Operator Instead of Bit Shift

4. Attempting Recursive Mirror Construction

5. Edge Case Handling for n=0

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings