4 lines C++ code.

  • 19

    You can also view more solution on Github

    class Solution {
        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.

  • 0

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

  • 0

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

  • 0

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

Log in to reply

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