[LeetCode] Gray Code

Gray Code -- binary numerical system where two successive values differ only in one bit (Wikipedia).

1. Background Information
1.1 Generate n-bit Gray Code
2-bit
00
01
11
10

3-bit
000
001
011
010
110
111
101
100

n-bit Gray Code can be generate from the list of (n -1) bit Gray Code using the following steps:
a. Let the list of (n - 1)-bit Gray Code be L1. Create another list L2 which is reverse of L1.
b. Modify the list L1 by prefixing a '0' in all codes of L1.
c. Modify the list L2 by prefixing a '1' in all codes of L2.
d. Concentrate L1 and L2. The concatenated list is required list of n-bits Gray Code.


1.2 n-th Gray Code
G(N) = (B(n) / 2) XOR B(n)


2. [LeetCode]
2.1 Problem

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.

2.2 Answer to this problem:
///////////////////////////////////////////////////////////////////////
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        //G(N) = (B(n)/2) XOR B(n)
        //Attention:
        // Two to the power of n, Use "Math.pow(2 , n);"
        // "^" Means XOR as an operator 
        
        ArrayList<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < Math.pow(2 , n); i++){
            int curGrayCode = (i / 2) ^ i;
            result.add(curGrayCode);
        }
     
        return result;
    }
}
///////////////////////////////////////////////////////////////////////