(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

Thoughts:
The tricky part of this question is to recognize the recursive structure here. For n = 0, sol = [0], that’s the base case. For recursive step, let’s take n = 2 and n = 3 as examples. n = 2, sol = [0, 1, 3, 2]; n = 3, sol = [0, 1, 3, 2, 6, 7, 5, 4]. Look at these two solutions, we see when n = 3, we add 4 more elements [6, 7, 5, 4] and they are just [2+4, 3+4, 1+4, 0+4]. That is sol(n+1) = sol(n) + [ reverse(sol(n)) + 2^(n) ].

Code (Java):

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> sol = new ArrayList<Integer>();
        if(n == 0) {
            sol.add(0);
            return sol;
        } else {
            ArrayList<Integer> previous = grayCode(n - 1);
            sol.addAll(previous);
            for(int i = previous.size() - 1; i >= 0; --i) {
                sol.add((int)Math.pow(2.0, n - 1) + previous.get(i));
            }
            return sol;
        }
    }
}

Code (C++):

class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) {
            vector<int> sol;
            sol.push_back(0);
            return sol;
        } else {
            vector<int> previous = grayCode(n - 1);
            vector<int> sol(previous);
            for(int i = previous.size() - 1; i >= 0; --i) {
                sol.push_back((int)pow(2.0, n - 1) + previous[i]);
            }
            return sol;
        }
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: