LeetCode: Gray Code

he 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

Solution:

Got a vague impression of this problem. Must have learned something about it before.
After checking out the definition of Gray Code, as shown here how to recursively get Kth gray code from (K-1)th one:

2-bit list:	00, 01, 11, 10
Reflected:		10, 11, 01, 00
Prefix old entries with 0:	000, 001, 011, 010,
Prefix new entries with 1:		110, 111, 101, 100
Concatenated:	000, 001, 011, 010,	110, 111, 101, 100

we can get 2th Gray Code for 0,1 by
0 1 (1 0)--> 00 01 11 10
See the code:

Note: Math.pow(2, i) == 1<<i

	public ArrayList<Integer> grayCode(int n) {
	if(n<0) return null;
	ArrayList<Integer> ret = new ArrayList<Integer>();
	if(n==0) {
	ret.add(0);
	return ret;
	}
	ret.add(0);
	ret.add(1);
	for(int i =2; i<=n; i++){
	for(int j=(1<<i-1)-1; j>=0; j--)
	{
	int m = ret.get(j);
	ret.add(m|1<<i-1);
	}
	}
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub