[LeetCode 89] Gray Code - Woodstock Blog

Question

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:

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.

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a qure mathematics question.

Gray Code is a very classic binary system, and we shall keep in mind clearly of its mathematical solution.

Solution

My solution is using recursion. First get the answer of input value = (n-1), then from that list, generate answer for input = n. A post talked about this.

The math approach to solve this problem is much more simpler. The (i)th element of Gray Code is calculated by the following method (I learnt from this blog):

binaryToGray = (i >> 1) ^ i;

For example,

00 -> 00

01 -> 01

10 -> 11

11 -> 10

Code

First, my solution

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    if (n == 0) {
        ans.add(0);
        return ans;
    }
    ArrayList<Integer> half = grayCode(n-1);
    ans.addAll(half);
    for (int i = half.size() - 1; i >= 0; i -- ) 
        ans.add(half.get(i) + (int)Math.pow(2, n-1));
    return ans;
}

Second, math solution

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    for (int i = 0; i < 1 << n; i ++) 
        ans.add((i >> 1) ^ i);
    return ans;
}