C++ iterative solution based on bit shifting


  • 0
    C

    My observation is basically a way to transcode from index 0 to 2^n-1 into the gray code. Each bit of the grey code is a function of (i,j), where i is the index of the current number in the vector and j is the current bit operating on the number. The value of the bit is basically xor of two bits in i.

    vector<int> grayCode(int n) {
        vector<int> result;
    
        for (int i = 0; i < (1 << n); i++) {
            int step = 0;
            for (int j = 0; j < n; j++) {
                int b = ((1 << j) & i) ^ (((1 << (j+1)) & i) >> 1);
                step = step + b;
            }
            result.push_back(step);
        }
        return result;
    }

Log in to reply
 

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