# 89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer *n* representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

**Example 1:**

```
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1
```

**Example 2:**

```
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].
```

```cpp
// Bit manipulation for gray code
vector<int> grayCode(int n) { // time: O(2^n); space: O(2^n)
    vector<int> res(1 << n);
    for (int i = 0; i < (1 << n); ++i) {
        res[i] = i ^ (i >> 1);
    }
    return res;
}
```

```cpp
// Iteration
// 2 numbers in the middle only differ at their most significant bit
vector<int> grayCode(int n) { // time: O(2^n); space: O(2^n)
    vector<int> res;
    res.reserve(1 << n);
    res.push_back(0);
    for (int i = 0; i < n; ++i) {
        for (int j = res.size() - 1; j >= 0; --j) {
            res.push_back(res[j] | (1 << i));
        }
    }
    return res;
}
```

```cpp
// Backtracking
void helper(vector<int>& res, const int& bits, const int& k) {
    if (k == 0) res.push_back(bits);
    else {
        helper(res, bits, k - 1);
        helper(res, bits ^ ((1 << k) - 1), k - 1);
    }
}
vector<int> grayCode(int n) { // time: O(2^n); space: O(2^n)
    vector<int> res;
    res.reserve(1 << n);
    int bits = 0;
    helper(res, bits, n);
    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/math/89.-gray-code.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.