# 89 Gray Code – Medium

### Problem:

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.

### Thoughts:

key idea is that to generate gray code list for n, add 1<<(n-1) with the reverse order of the list for gray code n-1.

0: {0}

1: {0} + {1} 1<<0 = 1

2: {0,1} + {11, 10} 1<< 1 = 10

3: {0, 1, 11, 10} + {110, 111, 101, 100}1 << 2 = 100

### Solutions:

``````public class Solution {
public List<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < n; i ++){
int offset = 1 << i;
for (int j = result.size() -1 ; j >= 0; j --){
int toAdd = result.get(j) + offset;
}
}
return result;
}
}
``````

Updated: 11/10/2016 This is an alternative, is a little bit more straightforward thinking, but this is taking more time than the solution above. Because it’s checking a lot of same element. But this solution is easier to come up with.

``````public class Solution {
public List<Integer> grayCode(int n) {
process(0, n, result);
return result;
}
private void process(int num, int n , List<Integer> result) {
for (int i = 0; i < n; i ++) {
int mask = 1 << i;
int tmp = num ^ mask;
if (!result.contains(tmp)) {