Gray Code

LeetCode 89 | Difficulty: Medium

Medium

Problem Description

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*.

Example 1:

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

Example 2:

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

Constraints:

- `1 <= n <= 16`

Topics: Math, Backtracking, Bit Manipulation

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 428 ms)

Metric	Value
Runtime	428 ms
Memory	N/A
Date	2018-01-31

Solution

public class Solution {
    public IList<int> GrayCode(int n) {
        List<int> res = new List<int>();
res.Add(0);
for (int i = 0; i < n; i++)
{
    int size = res.Count;
    for (int k = size-1; k >= 0; k--)
    {
        res.Add(res.ElementAt(k) | 1<< i);
    }
}

return res;
    }
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.