Share my solution

• My idea is to generate the sequence iteratively. For example, when n=3, we can get the result based on n=2.
00,01,11,10 -> (000,001,011,010 ) (110,111,101,100). The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one. It is easy to see its correctness.
Code is simple:

``````public List<Integer> grayCode(int n) {
List<Integer> rs=new ArrayList<Integer>();
for(int i=0;i<n;i++){
int size=rs.size();
for(int k=size-1;k>=0;k--)
}
return rs;
}``````

• It's very nice! THX!!!!!!!!!!!!!!!!!!!!

• Great, explanation ..Love

• Just so easy to understandTHX

• Great idea to deal with the 2^n loop

• So understandable!!!! Thx!

• Brilliant idea ! very impressive !

• I just change the
to

Then the answer went wrong. For example, if n==2, it would go to [0, 1, 4, 2]. How does this come out? Any ideas? Thank you!

• This post is deleted!

• @perfecttt can you add a () and try again? i.e.:

• @perfecttt 1 | 1 = 1. 1 + 1 = 2.

• This is the code you want to write in an interview... great job
The other short solutions are great. But you just dont know how to explain it, which would be useless.

• @vli02
Thanks, it becomes right by adding the parenthesis. Whenever I use << or >>, I should pay attention to add ().

• THX, really nice solution, here is C++ version,

``````    vector<int> grayCode(int n) {
vector<int>res(1,0);
for(int i=0;i<n;i++){
int size=res.size();
for(int j=size-1;j>=0;j--){
res.push_back(res[j]|1<<i);
}
}
return res;
}
``````

• this post is deleted!

• whats the complexity ?. Also we need only n numbers but here we are pushing into res more then n times. first loop with i runs n times and internal loop runs 0,1,2,..n-1 times ? so basically n2 numbers. Am i missing anything ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.