# What is the best solution for Gray Code problem? No extra space used and no recursion?

• I have a solution here which takes O(1) on space and no recursion used. Is this the best possible solution? (I combined the base cases in the loop as mike3 does. Thanks mike3!)

``````vector<int> grayCode(int n)
{
vector<int> result(1, 0);
for (int i = 0; i < n; i++) {
int curCount = result.size();
// push back all element in result in reverse order
while (curCount) {
curCount--;
int curNum = result[curCount];
curNum += (1<<i);
result.push_back(curNum);
}
}
return result;
}``````

• Not sure why you have the `if(n==1)` in there. Seems like that would just skip over the for loop and return at the end. Anyways, here's my Java version. We apparently have the same algorithm.

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

}

• Thanks for your comments. We have same algorithm but apparently your codes are more readable. I need to combine base cases inside the loop as you did.

• here is a simple python code for this problem, actually I just skipped the Gray Code generation part...

``````def grayCode(self, n):
if n == 0: return [0]
result = [0, 1]
for i in xrange(1, n):
result += [(x + 2**i) for x in reversed(result)]
return result``````

• If you take a second look you will notice that `n=0` isn't a corner case, set `result = [0]` and loop start from `0`

• ``````class Solution:
# @return a list of integers
def grayCode(self, n):
num = 2**n
return map(lambda x:(x>>1)^x,[x for x in range(num)])
``````

after I check the wikipedia what's the Gray Code, then, It's easy.

• Yes, it is a way to generate. Have you tried a recursive way? Even though someone doesn't know Gray Code is like that, it is possible to solve it.

• This post is deleted!

• Thanks for your post. However it would be better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.

• if n=2 we got [00,01,11,10], the next number will be 110 which add an 1 in front of last element 10. we can generate other element when n=3.
110:don't change any bit of 110, i.e. 110^00
111:change the last bit of 110, i.e. 110^01
101:change the last two bits of 110, i.e. 110^11
101:change the second bits of 110, i.e. 110^10
so it is easy to write such code below:

``````class Solution:
# @return a list of integers
def grayCode(self, n):
ret=[0]
for i in range(n):
start_num=ret[-1]|(1<<i)
ret.extend([start_num^elem for elem in ret])
return ret``````

• Counting from 0, when we generate v[i] from v[i-1], we just need to change bit where the rightmost bit 1 locates in i. For example, [00, 01, 11, 10], when we generate 11(2nd) from 01(1st), we just xor 01 with 10(rightmost bit 1 of 2); when we generate 10(3th) from 11(2nd), we just xor 11 with 01(rightmost bit 1 of 3). Here I use "i&-i" to get the rightmost bit 1 of i.

``````vector<int> grayCode(int n) {
vector<int> v(1,0);
for (int i=1;i<(1<<n);i++) v.push_back(v[i-1]^(i&-i));
return v;
}
``````

• I don't get how does this work: (x>>1)^x? Could you please explain more? Thanks!!

• http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code
I said above, the wikipedia helps me. May it will help you also.

• ``````vector<int> grayCode(int n) {

int m = pow(2,n); // total numbers

vector<int> res;

// http://en.wikipedia.org/wiki/Gray_code
for (int i = 0;i<m;i++)
{
int temp = (i>>1)^i; // generating the gray code
res.push_back(temp);
}
return res;
}
``````

• Same idea here ...
Our answers should be the best...

``````class Solution {
public:
vector<int> grayCode(int n) {

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

• A different way of solving this problem. Not smart, but a different idea

``````	//try to generate all possible code by 0 1-> 0+0 0+1 1+1 1+0 ->...
//add 0 at begin forward the array such as 0 1 -> 00 01
//add 1 at begin reverse the array such as 0 1 -> 11 10
public List<Integer> grayCode(int n) {
List<Integer> outlist = new ArrayList<Integer>();
if(n == 0) {
return outlist;
}

List<String> list = new ArrayList<String>();

for(int i = 0; i < n - 1; i++) {
List<String> tlist = new ArrayList<String>();
int listLen =  list.size();
for(int j = 0; j < listLen; j++) {
}
for(int j = 0; j < listLen; j++) {
tlist.add("1" + list.get(list.size() - 1 - j));
}
list = tlist;
}

for(String s : list) {
}
return outlist;
}``````

• This is brilliant!

• I also come up with a similar algorithm. But yours is more succinct. Thanks!

• ``````class Solution:
# @return a list of integers
def grayCode(self, n):
if n==0:
return [0]
result=[]
result.append(0)
result.append(1)

cur=2

while cur<=n:
i=(1<<(cur-1))-1
j=1<<(cur-1)
while i>=0:
result.append(result[i]+j)
i-=1
cur+=1

return result
``````

the same idea. copy reversely and add 1 to the end of each of it

• more short codes, use i ^ (i / 2)

``````class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ret = {0};
int nums = pow(2, n);
for (int i = 1; i < nums; ++i) ret.push_back(i ^ (i / 2));
return ret;
}
};``````

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