# Gray Code
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/gray-code)
Canonical: https://scaleengineer.com/dsa/problems/gray-code
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google)
---
## Problem
An **n-bit gray code sequence** is a sequence of `2n` integers where:

* Every integer is in the **inclusive** range `[0, 2n - 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`

# Approaches
## Backtracking
This approach treats the problem as a graph traversal problem. We can think of the numbers from `0` to `2^n - 1` as nodes in a graph. An edge connects two nodes if their binary representations differ by exactly one bit. The goal is to find a path that starts at `0` and visits every single node exactly once (a Hamiltonian path). A Depth First Search (DFS) with backtracking is a natural way to explore such paths.
**Time:** O(n * 2^n) · **Space:** O(2^n)
**Pros:** It is a general approach that can find any valid Gray code sequence, not just a specific one.; The logic directly follows the definition of the problem, making it conceptually straightforward.
**Cons:** Significantly less efficient than other approaches with a time complexity of `O(n * 2^n)`.; The overhead of recursion and state management (the `visited` array and the result list) makes it slower in practice.
### Explanation
We start with a path containing only `0`. We then recursively try to extend this path. At each step, we look at the last number added to our path and try to find a valid next number. A valid next number is one that differs by only one bit from the current number and has not been visited yet. We can find potential next numbers by flipping each of the `n` bits of the current number one at a time. If we find an unvisited valid neighbor, we add it to our path and recurse. If the recursive call eventually leads to a full path of length `2^n`, we have found our solution. If we hit a dead end (a number from which all valid neighbors have already been visited, but the path is not yet complete), we backtrack by removing the last number from the path and trying a different neighbor.

```java
class Solution {
    List<Integer> result;
    boolean[] visited;
    int n;

    public List<Integer> grayCode(int n) {
        this.n = n;
        result = new ArrayList<>();
        // Total numbers are 2^n
        int totalNumbers = 1 << n;
        visited = new boolean[totalNumbers];
        
        result.add(0);
        visited[0] = true;
        
        backtrack();
        return result;
    }

    private boolean backtrack() {
        if (result.size() == (1 << n)) {
            return true;
        }

        int current = result.get(result.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (!visited[next]) {
                visited[next] = true;
                result.add(next);
                if (backtrack()) {
                    return true;
                }
                // Backtrack
                result.remove(result.size() - 1);
                visited[next] = false;
            }
        }
        return false;
    }
}
```
### Algorithm
- Model the problem as finding a Hamiltonian path in a graph where vertices are numbers `0` to `2^n - 1` and an edge exists if two numbers differ by one bit.
- Use Depth First Search (DFS) to find a path that visits every vertex exactly once.
- Start the search from `0`.
- Maintain a `visited` array to avoid cycles and redundant computations.
- A recursive function `backtrack()` attempts to extend the current path:
  1. **Base Case:** If the path length is `2^n`, a solution is found. Return `true`.
  2. **Recursive Step:** Get the last number in the path, `current`.
  3. Iterate through all `n` possible bit flips of `current` to find potential `next` numbers.
  4. If a `next` number has not been visited:
     - Add it to the path and mark it as visited.
     - Recursively call `backtrack()`.
     - If the recursive call returns `true`, propagate `true` up the call stack.
     - If it returns `false`, backtrack by removing `next` from the path and unmarking it as visited.
  5. If all neighbors have been explored without finding a complete path, return `false`.

## Iterative Construction by Reflection
A more efficient method is to construct the Gray code sequence iteratively. This approach leverages the reflective property of binary-reflected Gray codes. We can generate the `n`-bit Gray code sequence from the `(n-1)`-bit sequence. The `n`-bit sequence is formed by taking the `(n-1)`-bit sequence, followed by the same sequence in reverse order with the most significant bit set to 1.
**Time:** O(2^n) · **Space:** O(2^n)
**Pros:** Much more efficient than backtracking, with a time complexity of `O(2^n)`.; The constructive approach is intuitive and avoids the complexity of searching.; Implementation is concise and does not require recursion.
**Cons:** While efficient, the logic of modifying a list while iterating over it can be slightly tricky to get right.; It generates only one specific type of Gray code sequence (the binary-reflected one).
### Explanation
Let's illustrate with an example for `n=3`.
- **n=1:** The sequence is `[0, 1]`. (Binary: `[0, 1]`)
- **n=2:** We take the `n=1` sequence `[0, 1]`. Its reverse is `[1, 0]`. We add `2^1 = 2` to the reversed sequence, getting `[3, 2]`. Concatenating gives `[0, 1, 3, 2]`. (Binary: `[00, 01, 11, 10]`)
- **n=3:** We take the `n=2` sequence `[0, 1, 3, 2]`. Its reverse is `[2, 3, 1, 0]`. We add `2^2 = 4` to the reversed sequence, getting `[6, 7, 5, 4]`. Concatenating gives `[0, 1, 3, 2, 6, 7, 5, 4]`.

This iterative process can be implemented efficiently. We start with a list containing just `0`. In each iteration `i` from `0` to `n-1`, we double the size of the list by iterating through the current elements in reverse and adding `1 << i` to them.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        
        for (int i = 0; i < n; i++) {
            int size = result.size();
            // The value to be added to form the reflected part
            int head = 1 << i;
            // Iterate backwards through the current list
            for (int j = size - 1; j >= 0; j--) {
                result.add(head + result.get(j));
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Start with the base case for a 1-bit Gray code, which is `[0, 1]`.
- Iteratively build the sequence for `i` bits from the sequence for `i-1` bits, for `i` from 2 to `n`.
- To construct the `i`-bit sequence:
  1. Take the existing `(i-1)`-bit sequence (let's call it `L1`).
  2. Create a reversed copy of `L1` (let's call it `L2`).
  3. The new `i`-bit sequence is formed by two parts:
     - The first part is the elements of `L1` (with a `0` prepended in binary, which doesn't change their value).
     - The second part is the elements of `L2` with `2^(i-1)` added to each element (which is equivalent to prepending a `1` in binary).
- In implementation, we can do this in place:
  1. Start with `result = [0]`.
  2. Loop `i` from `0` to `n-1`.
  3. In each iteration, iterate backwards through the current `result` list.
  4. For each element `x` from the backwards iteration, add `x + (1 << i)` to the end of the `result` list.

## Direct Generation using Mathematical Formula
The most efficient and elegant solution involves using a direct mathematical formula. There's a well-known property that connects the `i`-th integer with its corresponding value in the binary-reflected Gray code sequence. This allows us to generate each number in the sequence directly, without reference to the other numbers.
**Time:** O(2^n) · **Space:** O(2^n)
**Pros:** Extremely efficient with `O(2^n)` time complexity and minimal overhead per operation.; The implementation is the simplest and most concise.; Each element is calculated independently, which makes the algorithm easy to reason about and potentially parallelizable.
**Cons:** The mathematical reasoning behind the formula `i ^ (i >> 1)` is not immediately obvious without prior knowledge of Gray codes.
### Explanation
The formula to convert a binary number `i` to its Gray code equivalent is `G(i) = i ^ (i >> 1)`, where `^` is the bitwise XOR operator and `>>` is the right shift operator. By applying this formula for all integers from `0` to `2^n - 1`, we can generate the entire Gray code sequence.

For example, for `n=3`:
- `i=0`: `0 ^ (0>>1) = 0 ^ 0 = 0`
- `i=1`: `1 ^ (1>>1) = 1 ^ 0 = 1`
- `i=2`: `2 ^ (2>>1) = 2 ^ 1 = 3` (Binary: `010 ^ 001 = 011`)
- `i=3`: `3 ^ (3>>1) = 3 ^ 1 = 2` (Binary: `011 ^ 001 = 010`)
...and so on.

This approach is highly efficient because it involves a simple loop and constant-time bitwise operations inside it.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> grayCode(int n) {
        int size = 1 << n;
        List<Integer> result = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}
```
### Algorithm
- The `k`-th Gray code in a binary-reflected sequence can be calculated directly from the integer `k`.
- The formula is `Gray(k) = k XOR (k >> 1)`.
- The algorithm is as follows:
  1. Determine the total number of codes to generate, which is `size = 2^n`.
  2. Create a result list.
  3. Loop with an index `i` from `0` to `size - 1`.
  4. In each iteration, calculate the Gray code value using the formula: `i ^ (i >> 1)`.
  5. Add the calculated value to the result list.
  6. Return the list after the loop finishes.

# Solutions
### Java

```java
int gray ( x ) { return x ^ ( x >> 1 ); }
```

### JavaScript

```javascript
/** * @param {number} n * @return {number[]} */ var grayCode = function (n) {
  const ans = [];
  for (let i = 0; i < 1 << n; ++i) {
    ans.push(i ^ (i >> 1));
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> grayCode(int n) {
    vector<int> ans;
    for (int i = 0; i < 1 << n; ++i) {
      ans.push_back(i ^ (i >> 1));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def grayCode(
        self, n: int) -> List[int]: return [i ^ (i >> 1) for i in range(1 << n)]

```