LeetCode Problem 89

Difficulty: 🟡 Medium
Topics: Math, Backtracking, Bit Manipulation

Solution

LeetCode 89 - Gray Code

Problem Understanding

The problem asks us to generate a valid Gray code sequence for a given number of bits, n.

A Gray code sequence is a special ordering of numbers where every adjacent pair differs by exactly one bit in binary form. In addition, the sequence is cyclic, meaning the first and last numbers must also differ by exactly one bit.

For an n-bit Gray code:

• There are exactly 2^n distinct numbers.
• Every number must be between 0 and 2^n - 1.
• The sequence must start with 0.
• No number can appear more than once.
• Consecutive numbers must differ by exactly one binary bit.

The input n represents the number of bits available in each binary number. For example:

• If n = 2, valid numbers range from 0 to 3.
• If n = 3, valid numbers range from 0 to 7.

The output can be any valid Gray code ordering. Multiple correct answers may exist.

The constraints are relatively small:

• 1 <= n <= 16

This means the maximum sequence size is:

$$2^{16} = 65536$$

Generating all numbers is completely feasible, but exponential brute force search would still be too expensive if implemented poorly. The problem strongly hints that there is a mathematical construction or bit manipulation trick that directly generates Gray codes efficiently.

Several edge cases are important:

• n = 1, the smallest possible input
• Larger values like n = 16, where inefficient backtracking may become impractical
• Ensuring the first and last elements also differ by exactly one bit
• Avoiding duplicate numbers

The problem guarantees valid input, so we do not need to handle negative values or zero.

Approaches

Brute Force Approach

A brute force solution would attempt to build the sequence incrementally using backtracking.

The idea is:

1. Start with 0
2. Try every unused number
3. Check whether it differs by exactly one bit from the previous number
4. Continue recursively until all 2^n numbers are used
5. Finally verify that the last number differs by one bit from the first

To determine whether two numbers differ by exactly one bit, we can use XOR:

$$a \oplus b$$

If the result contains exactly one set bit, then the numbers differ by one bit.

This approach is correct because it explores all possible valid sequences until one satisfies the Gray code conditions.

However, the search space becomes enormous very quickly. There are potentially (2^n)! permutations to explore in the worst case. Even with pruning, this becomes impractical for larger values of n.

Optimal Approach

The key insight is that Gray codes have a direct mathematical formula.

For a number i, its Gray code representation is:

$G(i)=i\oplus(i\gg1)$

This formula works because shifting i right by one bit aligns adjacent binary bits, and XOR highlights where changes occur.

The resulting sequence naturally satisfies the Gray code property:

• Adjacent numbers differ by exactly one bit
• All numbers are unique
• The sequence starts at 0
• The sequence is cyclic

Instead of searching for a valid ordering, we directly construct one in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((2^n)!)	O(2^n)	Backtracking over permutations
Optimal	O(2^n)	O(2^n)	Direct Gray code formula using bit manipulation

Algorithm Walkthrough

Optimal Algorithm

1. Compute the total number of Gray codes needed.

Since an n-bit sequence contains every possible n-bit number exactly once, we need:

$$2^n$$

values. 2. Initialize an empty result list.

This list will store the generated Gray codes in order. 3. Iterate from 0 to 2^n - 1.

Each integer i corresponds to one position in the Gray code sequence. 4. Convert i into its Gray code representation.

Use the formula:

$gray=i\oplus(i\gg1)$

Here:

• i >> 1 shifts all bits right by one position
• XOR compares adjacent bit positions
• The result changes only one bit between consecutive values

5. Append the Gray code value to the result list.

Because the formula guarantees uniqueness and proper adjacency, no additional validation is required. 6. Return the completed list.

After processing all values, the result contains a valid Gray code sequence.

Why it works

The formula works because consecutive integers differ in predictable binary patterns. When we XOR a number with itself shifted right by one bit, the resulting transformation ensures that only one output bit changes between consecutive values.

This construction preserves the Gray code property across the entire sequence, including the transition from the last element back to the first.

Python Solution

from typing import List

class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = []
        
        total_numbers = 1 << n
        
        for number in range(total_numbers):
            gray = number ^ (number >> 1)
            result.append(gray)
        
        return result

The implementation begins by calculating the total number of values required using 1 << n, which computes 2^n efficiently with bit shifting.

We then iterate through every integer from 0 to 2^n - 1.

For each value, we apply the Gray code formula:

gray = number ^ (number >> 1)

The right shift aligns neighboring bits, and XOR produces the transformed Gray code value.

Each generated Gray code is appended to the result list. Since the formula guarantees correctness, we do not need additional duplicate checks or adjacency verification.

Finally, the completed sequence is returned.

Go Solution

func grayCode(n int) []int {
    totalNumbers := 1 << n
    
    result := make([]int, 0, totalNumbers)
    
    for number := 0; number < totalNumbers; number++ {
        gray := number ^ (number >> 1)
        result = append(result, gray)
    }
    
    return result
}

The Go implementation closely mirrors the Python solution.

A slice is created with preallocated capacity using:

make([]int, 0, totalNumbers)

This reduces reallocations during appends.

Bit operations in Go behave similarly to Python for nonnegative integers, so the same Gray code formula applies directly.

Since n <= 16, integer overflow is not a concern in Go.

Worked Examples

Example 1

Input:

n = 2

Total numbers:

$$2^2 = 4$$

We iterate from 0 to 3.

number	Binary	number >> 1	XOR Result	Gray Code
0	00	00	00	0
1	01	00	01	1
2	10	01	11	3
3	11	01	10	2

Final result:

[0, 1, 3, 2]

Binary representation:

00
01
11
10

Adjacent pairs differ by one bit:

• 00 -> 01
• 01 -> 11
• 11 -> 10
• 10 -> 00

All transitions change exactly one bit.

Example 2

Input:

n = 1

Total numbers:

$$2^1 = 2$$

number	Binary	number >> 1	XOR Result	Gray Code
0	0	0	0	0
1	1	0	1	1

Final result:

[0, 1]

The only adjacent transition changes one bit.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	We generate each Gray code exactly once
Space	O(2^n)	The output list stores all generated values

The algorithm processes every required number exactly once. Each iteration performs only constant time bit operations, making the runtime linear in the size of the output.

The space complexity is also linear because the result array must store all 2^n Gray codes.

Test Cases

from typing import List

def differs_by_one_bit(a: int, b: int) -> bool:
    xor_value = a ^ b
    return xor_value != 0 and (xor_value & (xor_value - 1)) == 0

def validate_gray_code(sequence: List[int], n: int) -> bool:
    expected_size = 1 << n
    
    if len(sequence) != expected_size:
        return False
    
    if sequence[0] != 0:
        return False
    
    if len(set(sequence)) != expected_size:
        return False
    
    for i in range(expected_size):
        current_value = sequence[i]
        next_value = sequence[(i + 1) % expected_size]
        
        if not differs_by_one_bit(current_value, next_value):
            return False
    
    return True

solution = Solution()

# Example 1
result = solution.grayCode(2)
assert validate_gray_code(result, 2)  # Standard 2-bit Gray code

# Example 2
result = solution.grayCode(1)
assert validate_gray_code(result, 1)  # Smallest valid input

# n = 3
result = solution.grayCode(3)
assert validate_gray_code(result, 3)  # Typical medium-sized case

# n = 4
result = solution.grayCode(4)
assert validate_gray_code(result, 4)  # Larger sequence validation

# Maximum constraint
result = solution.grayCode(16)
assert len(result) == 65536  # Stress test for upper bound

# Verify uniqueness for larger input
assert len(set(result)) == 65536  # No duplicates allowed

# Verify sequence starts with zero
assert result[0] == 0  # Problem requirement

Test	Why
n = 1	Validates smallest input
n = 2	Matches provided example
n = 3	Tests typical behavior
n = 4	Verifies larger cyclic sequence
n = 16	Stress test for upper constraint
Uniqueness check	Ensures no duplicates
Start with zero	Confirms required starting condition

Edge Cases

Smallest Possible Input

When n = 1, the sequence contains only two numbers:

[0, 1]

This case is important because some implementations accidentally assume at least two bit positions exist. The formula-based approach works naturally even for a single bit.

Maximum Constraint

When n = 16, the sequence contains 65536 numbers. Recursive backtracking approaches may become extremely slow or consume excessive memory.

The direct mathematical construction avoids this problem entirely because each value is generated independently in constant time.

Cyclic Adjacency Requirement

A common mistake is validating only neighboring elements inside the array while forgetting that the first and last elements must also differ by one bit.

The Gray code formula inherently produces a cyclic sequence, so this condition is automatically satisfied without extra logic.

Duplicate Values

Incorrect bit manipulations can accidentally produce repeated values, violating the uniqueness requirement.

The formula:

$G(i)=i\oplus(i\gg1)$

creates a one-to-one mapping between integers and Gray codes, guaranteeing uniqueness across the entire sequence.