LC 89 Grey code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2 Output: [0,1,3,2] Explanation: 00 – 0 01 – 1 11 – 3 10 – 2

For a given n, a gray code sequence may not be uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence.

Mirror grey code

We want to find a map between binary and grey code. For 1 bit: 0 is mapped to 0, and 1 is mapped to 1. The binary is the same as grey code.

For 2 bits:

<br />binary   gery    binary(2)   gery(2)
0         0       00          00
1         1       01          01
                             ____
                  10          11
                  11          10

To recursive generate grey code of bit size 2, we will build upon gray code of size 1. We want to generate 4 numbers whose binary representation differ only in 1 bit. If we already have gray code of size n, then if we mirror imaged the gray code, then the upper and lower part are both valid gray code of size(n). To generate gray code 2n, we will just add 0 to the first half and 1 to the second half.

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<string> res = binGrayCode(n);
        vector<int> intRes;
        for(int i = 0; i < res.size(); i ++){
            intRes.push_back(std::stoi(res[i], nullptr, 2));
        }
        return intRes;
    }

    vector<string> binGrayCode(int n ){
        if(n == 0){
            vector<string> vect{"0"};
            return vect;
        }
        if(n == 1){
            vector<string> vect{"0", "1"};
            return vect;
        }
        vector<string> firstHalf = binGrayCode(n - 1);
        vector<string> mirrorHalf = firstHalf;
        reverse(mirrorHalf.begin(), mirrorHalf.end());

        for(int i = 0; i < firstHalf.size(); i ++){
            firstHalf[i] = "0" + firstHalf[i];
            mirrorHalf[i] = "1" + mirrorHalf[i];
        }


        firstHalf.insert(firstHalf.end(), mirrorHalf.begin(), mirrorHalf.end());
        return firstHalf;
    }



};

Iterative approach


class Solution { public: vector<int> grayCode(int n) { vector<int> res(1, 0); for(int i = 0; i < n; i ++){ //creating i+1 bit gray code int mirrorBoundary = res.size(); while(mirrorBoundary > 0){ mirrorBoundary --; //add 1 to the most significant bit int mirroredNum = res[mirrorBoundary]; mirroredNum += 1<<(i); res.push_back(mirroredNum); } } return res; } };

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax