LeetCode: 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.

---

We can generate the gray codes by bootstrapping. If n is 1, there is only 0 and 1 in the final set. If n is 2. We can generate by adding a 0 to all the elements in set of 1 bit. And then adding a 1 to all elements in the set of 1 bit in reverse order. Here is a example:

n = 1; {0, 1}

n = 2; {00, 01} => {00, 01, 11, 10}

n = 3; {000, 001, 011, 010} => {000, 001, 011, 010, 110, 111, 101, 100}

C++ Code:

/*
 * func: gray_code
 * goal: generate gray code of given bits
 * @param n: the number of bits
 * return: a vector of all codes in decimal
 */
vector<int> gray_code(int n){
    vector<int> code;
    if(n <= 0){
        code.emplace_back(0);
        return code;
    }
    if(n == 1){
        code.emplace_back(0);
        code.emplace_back(1);
        return code;
    }
    vector<int> tmp_code = gray_code(n-1);
    int offset = 1 << (n-1);
    for(int i=0; i<tmp_code.size(); i++){
        code.emplace_back(tmp_code[i]);
    }
    for(int i = tmp_code.size()-1; i >= 0; --i){
        code.emplace_back(offset + tmp_code[i]);
    }
    
    return code;
}

Python Code:

# func: generate gray codes of given bits
# @param n: the number of bits
# @return: a list of integers
def gray_code(n):
    if n <= 0:
        return [0]
    str_result = ['0', '1']
    for _ in xrange(n-1):
        stack = str_result[:]
        for i in xrange(len(str_result)):
            str_result[i] = '0' + str_result[i]
        for j in xrange(1, len(str_result)+1):
            str_result.append('1' + stack[-j])

    return [int(x, 2) for x in str_result]