### Question

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

**Note:**

For a given *n*, a gray code sequence is not uniquely defined.

For example, `[0,2,3,1]`

is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

### Stats

Frequency | 2 |

Difficulty | 4 |

Adjusted Difficulty | 3 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This is a qure mathematics question.**

Gray Code is a very classic binary system, and we shall keep in mind clearly of its mathematical solution.

### Solution

**My solution is using recursion**. First get the answer of input value = (n-1), then from that list, generate answer for input = n. A post talked about this.

**The math approach to solve this problem is much more simpler**. The (i)th element of Gray Code is calculated by the following method (I learnt from this blog):

binaryToGray = (i >> 1) ^ i;

For example,

00 -> 00

01 -> 01

10 -> 11

11 -> 10

### Code

**First, my solution**

```
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> ans = new ArrayList<Integer>();
if (n == 0) {
ans.add(0);
return ans;
}
ArrayList<Integer> half = grayCode(n-1);
ans.addAll(half);
for (int i = half.size() - 1; i >= 0; i -- )
ans.add(half.get(i) + (int)Math.pow(2, n-1));
return ans;
}
```

**Second, math solution**

```
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < 1 << n; i ++)
ans.add((i >> 1) ^ i);
return ans;
}
```