89. Gray 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.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

From my intuition, the problem is like Hanoi. If you're able to solve n = 2 case, then you can kind of repeat it twice to achieve n = 3 case. Lets try to extend n = 2 case to n = 3 case first.

When n = 2, the sequence is 00 -> 01 -> 11 -> 10 If you want to extend it to n=3 directly without modifying old part, there are only two possible sequence, and they are not hard to find out.

000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100

000 -> 001 -> 011 -> 010 -> 110 -> 100 -> 101 -> 111

So now, the problem is, which one should we choose. I would choose the first one for two reasons.

1. The last elements have similar form in both n=2 and n=3 case. They are 1 follows bunch of 0's. Since we hope to extend the same algorithm to n=4 n=5... cases. It's good to preserve some properties.

2. If we only look at the last 2 digits, we can see that in the first sequence, the second half is exact the reverse of the first half, that means, we can systematically generate the second half according to the first half.

 def grayCode(self, n):
        results = [0]
        for i in range(n):
            results += [x + pow(2, i) for x in reversed(results)]
        return results

class Solution {
public:
    vector<int> grayCode(int n) {
         vector<int> result(1, 0);        
        for (int i = 0; i < n; i++) {
            //求出当前结果中的数量
            int curCount = result.size();
            // 1<<i在加上上面结果的逆序就是所求的
            while (curCount) {
                curCount--;
                int curNum = result[curCount];
                curNum += (1<<i);
                result.push_back(curNum);
            } 
        }
        return result;
    }
};

[wiki gray code](https://en.wikipedia.org/wiki/Gray_code)

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.

        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        for(int i = 0; i < 1<<n; i++){
            res.push_back(i ^ i >>1);
        }
        return res;
    }
};