> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/gray-code.md).

# 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`.

For example, given n = `2`, return `[0,1,3,2]`. Its gray code sequence is:

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

There might be multiple gray code sequences possible for a given n.\
Return any such sequence.

```java
// Let G(n) represent a gray code of n bits.
// Note that reverse of G(n) is also a valid sequence.
// Let R(n) denote the reverse of G(n).

// Note that we can construct
// G(n+1) as the following :
// 0G(n)
// 1R(n)

// Where 0G(n) means all elements of G(n) prefixed with 0 bit and 1R(n) means all elements of R(n) prefixed with 1.
// Note that last element of G(n) and first element of R(n) is same. So the above sequence is valid.

// Example G(2) to G(3) :
// 0 00
// 0 01
// 0 11
// 0 10
// 1 10
// 1 11
// 1 01
// 1 00
public class Solution {
    public List<Integer> grayCode(int a) {
        int len = 1 << a;
        List<Integer> res = new ArrayList<>(len);
        res.add(0);
        for (int i = 1; i <= a; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                int next = res.get(j) | (1 << (i - 1));
                res.add(next);
            }
        }
        return res;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/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.