4 lines C++ code.

• You can also view more solution on Github

``````class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ans(1<<n);
for (int i=0; i<(1<<n); i++)
ans[i] = i^(i>>1);
return ans;
}
};
``````

I try to give a simple proof here. Let's denote i^(i>>1) as f(i). To proof f(i) is the ith gray code, we only need to prove the following statements:

1. f(0) = 0
2. (i) and f(i+1) only differs in one digit
3. f(i) is bijective, e.g. f(i) = f(j) if and only if i = j.

The first one is obvious.

For the second , f(i) ^ f(i+1) = i^(i>>1)^(i+1)^((i+1)>>1) = (i^(i+1)) ^ ((i^(i+1)) >> 1). Let's denote g(i) = i^(i+1), g(i) has the form of 0000111...111. So f(i) ^ f(i+1) = g(i) ^ g(i)>>1 = 00001000...000.

The third part can be proved alike.

• How did you find this method? Could you please provide some explanation to your solution?

• You can check out the following link from wikipedia which explains this: https://en.wikipedia.org/wiki/Gray_code

• I just tried to give a simple proof. Please see if there is any problem.

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