# 1ms Java Solution with explaination

• ``````public class Solution {
//analyze the pattern
//n=0  -> 0
//n=1  -> 0, 1
//n=2  -> (00,  01),  (10,  11)
//n=3  -> (000, 001, 010, 011), (111, 110, 101, 100)

//so the pattern is when n=n  -> add 0 in front of all the result of (n-1)'s binary value (This is just same as all the result of (n-1)
//                               and add 1 in front of all the result of(n-1)'s binary value (This need to calculate.)

public List<Integer> grayCode(int n) {
List<Integer> result = new ArrayList();

for(int i=1; i<=n; i++){
int front=1;
//Create the correct value for binary format (10...0) which the value has i digi
//so shift 1 to right (i-1) times
for(int j=1; j<i; j++){
front = front<<1;
}

//add the new generated value to the result list
//the new generated value is the last result add front value
int size=result.size();
//we want to loop through the (n-1) result from end to start. This is just because want to make the test case match the Leetcode answer. You can use other way loop through the (n-1) result.
for(int k=size-1; k>=0; k--){
}
}

return result;
}
``````

}

• Your pattern analysis is wrong, n=2 -> 00, 01, 11, 10. n=3 -> 000, 001, 011, 010, 110, 111, 101, 100

• Thanks, Ryanmax. You are right. It was the typo, and I just corrected it.

Tip: `size == front` in every iteration, because you double the elements in `result` each time and `i` advances by one which results in one more `front << 1 == front * 2`.

so shift 1 to right (i-1) times

VS the operator shifiting left

``````front<<1;
``````

and also there's a direct operation for it, no need to loop

``````int front = 1 << (i - 1);
``````

This is just because want to make the test case match the Leetcode answer. You can use other way loop through the (n-1) result.

This is simply not true. If you don't reverse the walk you simply ignore the reflective property of the Grey code, notice how after the `k`th line the last `k-1` bits are reflections of the elements before.

``````0000 ----\
----     |
0001 ---\|
----    ||
0011 --\||
0010 -\|||
----  |||| k = 3, reflection above and below
0110 -/|||
0111 --/||
0101 ---/|
0100 ----/
``````

This relfectivity makes sure that only one bit is flipped, consider what happens if we don't do a reverse walk when adding the prefix (`front == 0b100`):

``````000, 001, 011, 010, !, 100, 101, 111, 110
``````

at `!` the numbers differ in two bits: counting from right startin from 0 you need to flip bit 1 and bit 2 to go from `010` to `100`. Moving a bit is not allowed here. In other words XOR of two consecutive gray code elements must be a power of `2`.

• Some simplification:

``````public class Solution {
public List<Integer> grayCode(int n) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(n == 0) return list;