A simple Google search will reveal the secret behind Gray Code, of course. Knowing the formula, this question can be solved within 5 minutes. But what if I've never known anything about Gray Code? Is it feasible for someone to derive the formula during an interview? I think I would just get stuck for 45 minutes trying to figure out how to generate an algorithm for it. Is this question intended to test one's knowledge base?
What if I have no knowledge over Gray Code before?


Here is my take about Gray codes. Maybe other people might have different opinions.
1  You have to know what they are (it was even written in the problem statement)
The gray code is a binary numeral system where two successive values
differ in only one bit.2  You have to know what they are useful for.
3  You have to know that they are "symmetric".
With 1 and 3, you can solve any programming problem about Gray code you could have in an interview. I don't think anyone expect you to know the insandouts of the Gray code (well, unless you're applying to a computer architecture position), but people expect you to be able to derive algorithms from 1 and 3.
The point 2. is a nice touch to tell your interviewer.

I agree with loick. I don't think it's a knowledge base problem. It's also my first time to hear about Gray Code. But after trying some small cases, I still figured out an algorithm for it.
From my intuition, the problem is like Hanoi. If you're able to solve n = 2 case, then you can kind of repeat it twice to achieve n = 3 case. Lets try to extend n = 2 case to n = 3 case first.
When n = 2, the sequence is
00 > 01 > 11 > 10
If you want to extend it to n=3 directly without modifying old part, there are only two possible sequence, and they are not hard to find out.000 > 001 > 011 > 010 > 110 > 111 > 101 > 100
000 > 001 > 011 > 010 > 110 > 100 > 101 > 111
So now, the problem is, which one should we choose. I would choose the first one for two reasons.

The last elements have similar form in both n=2 and n=3 case. They are 1 follows bunch of 0's. Since we hope to extend the same algorithm to n=4 n=5... cases. It's good to preserve some properties.

If we only look at the last 2 digits, we can see that in the first sequence, the second half is exact the reverse of the first half, that means, we can systematically generate the second half according to the first half.
That's how I figured out the algorithm. Hope that helps!


I agree. In fact, having not heard of Gray Code before, I had a hard time under standing what "two successive values differ in only one bit means". In my original under standing, the following output should be valid for input n = 3:
000>010>011>001>101>111>110>100
so I was really not sure which test case will be tested. Thanks to @hslu, I understand what the problem wants and solved it like in 5 minutes. I don't think it has anything to do with mathematical formula.

Though I heard it before, I just in time find another method besides the methods metioned above or in Wikipedia by induction.
+2^k: i % 2^(k+2) == 2^k 2^k: i % 2^(k+2) == 2^k*3
means when
i % 2^(k+2) == 2^k
, thatA[i]  A[i1] = 2^k
;
wheni % 2^(k+2) == 2^k*3
, thatA[i]  A[i1] = 2^k
;No prove, but I pass the OJ.
Time cost is
O(n*2^n)
which I believe is the fastest algorithms.

Well, I was talking about the algorithm to generate those numbers, not including printing them out... So generate each number only takes 1 addition operation. So total time cost is roughly O(2^n). I guess we normally refer to computation cost rather than printing cost as the time complexity of algorithm.

I approached the problem with dynamic programming, or table building.
n = 1
0
1n=2
0 0
0 1
1 1
1 0n=3
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0After growing some rows and cols of the table, you can tell how to build table
n+1
from tablen
, namely add 1 to each row of tablen
, reverse it and append on tablen
. The actual operation is easier since the output only requires a list(not a nested list), so adding bit 1 to a table row is just add1<<(n1)
to the number that row represents.

I don't have knowledge about gray code, and my first mind is to bruteforce it.
The time complexity is O(n*(2^n)), slightly larger than O(2^n) ^_^
vector<int> grayCode(int n) { unordered_set<int> s{0}; vector<int> r{0}; for (int c = 0, i = 1; i < (1<<n); ++i) { for (int j = 0; j < n; ++j) { if (s.insert(c ^ (1<<j)).second) { r.push_back(c ^= (1<<j)); break; } } } return r; }

I use the same idea with @hsiu. Here is my python code:
class Solution: # @return a list of integers def grayCode(self, n): if n ==0: return [0] ret = [0,1] for i in range(1,n): ret = ret + [pow(2,i) + ret[x] for x in range(len(ret)1,1,1)] return ret

Actually there are several possible sequences when n=3 instead of just two as you've mentioned; besides I think knowing the formula will definitely increase the possibility of your to hack it more fluently otherwise it will dramatically exhaust your brain. One of the socalled several is as follows:
000>100>101>111>110>010>011>001