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

	class Solution {
	public:
	vector<int> grayCode(int n) {
	int p=0;
	vector<int> res;
	vector<int> flag(pow(2, n), 0);
	res.push_back(0);
	flag[0]=1;
	for(int i=1; i<pow(2, n); i++){
	for(int j=0; j<n; j++){
	int s=1<<j;
	if(flag[p^s]==0){
	flag[p^s]=1;
	res.push_back(p^s);
	p=p^s;
	break;
	}
	}
	}
	return res;
	}
	};

view raw Q89.cpp hosted with ❤ by GitHub

Rnd3 Sol:
No extra space used. Based on an observation that if two adjacent numbers are different by only 1 bit, than adding 1 to same 0 bit position of the two numbers should result in gray code too.

	vector<int> grayCode(int n)
	{
	vector<int> result(1, 0);
	for (int i = 0; i < n; i++) {
	int curCount = result.size();
	// push back all element in result in reverse order
	while (curCount) {
	curCount--;
	int curNum = result[curCount];
	curNum += (1<<i);
	result.push_back(curNum);
	}
	}
	return result;
	}

view raw 89Rnd3.cpp hosted with ❤ by GitHub