C++ Code (With Explanation)


  • 0
    G
        vector<int> grayCode(int n) {
            vector<int> gc;
            gc.reserve(pow(2, n));
            for (int bit = 0, mask = 1; bit <= n; bit++) {
                if (bit == 0) gc.push_back(0);    // First element is always 0 (given)
                else {
                    // Gray code with the new bit can be easily generated by iterating BACKWARDS
                    // the gray code we have generated so far and adding a '1' in the MSB.
                    //
                    // This works because the very first number with the new bit obviously
                    // differs with its previous in the MSB (1). From then on, although the MSB
                    // stays 1 the remaining bits are previously generated gray code, so they
                    // must differ only by 1 bit.
                    //
                    // Example: n = 4
                    // bit      gray_code
                    //  0       0
                    //  1       1{gray_code(0) iterating backwards}
                    //          {0, 1}
                    //  2       1{gray_code(1) iterating backwards}
                    //          {0, 1, 11, 10}
                    //  3       1{gray_code(2) iterating backwards}
                    //          {0, 1, 11, 10, 110, 111, 101, 100}
                    //
                    for (int j = pow(2, bit - 1) - 1; j >= 0; j--) {
                        gc.push_back(mask | gc[j]);
                    }
                    mask <<= 1;
                }
            }
            return gc;
        }
    

Log in to reply
 

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