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
C++:
01 vector<int> grayCode(int n) {
02     vector<vector<int> > A;
03     vector<int> t;
04     t.push_back(0);
05     A.push_back(t);
06     int pw=1;
07     for(int i=1;i<=n;i++){
08         vector<int>& p=A[i1];
09         vector<int> toAdd(p);
10         for(int j=p.size()1;j>=0;j)
11             toAdd.push_back(p[j]+pw);
12         pw=pw<<1;
13         A.push_back(toAdd);
14     }
15     return A[n];
16 }
Advertisements
This entry was posted in Bit operation, Dynamic programming. Bookmark the permalink.

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