4 lines C++ code.


  • 19
    Z

    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.


  • 0
    W

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


  • 0
    G

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


  • 0
    Z

    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.