# 89. Gray Code

### Description

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.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/generate-n-bit-gray-codes-set-2/)
* [Leetcode](https://leetcode.com/problems/gray-code/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-gray-code-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="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
{% endtab %}

{% tab title="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].
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> grayCode(int n) {
        int noOfGrays = (1 << n);
        return IntStream.range(0, noOfGrays)
            .mapToObj(i -> (i ^ (i>>1)))
            .collect(Collectors.toList());
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> grayCode(int n) {
        // Number of possible gray codes (i.e, 2^n)
        int noOfGrays = (1 << n);
        List<Integer> grayCodes = new ArrayList<>();
        for(int i = 0; i < noOfGrays; i++) {
            grayCodes.add(i ^ (i>>1));
        }
        return grayCodes;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* A backtracking approach to generate n bit Gray Codes - [GFG](https://www.geeksforgeeks.org/backtracking-approach-generate-n-bit-gray-codes/)


---

# 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://code-snippets.hbamithkumara.com/leetcode/problems/1-100/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.