LeetCode Gray Code: Backtracking vs Iterative Way

Overview

LeetCode Gray Code: By recursive definition (backtracking’s angle), gray code (n bits) = 0 1 +gray code (n-1 bits), and it could be done in a iterative way.

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

Solution and Precautions: Backtracking vs Iterative Way

Well, if you have ever learned about Gray code, it is actually known as reflected binary code, the name shows how this kind of code is constructed:  In a recursive way, gray code with n bits could be constructed from the gray code with n-1 bits.

(1) prefix all the gray code with n-1 bits with 0

(2) reverse the order of the n-1 bit gray code and prefix all of them with 1 (reflected)

(3) concatenate (1) and (2) to get the gray code of n bits

The following Java code is accepted by LeetCode OJ to pass this Gray Code problem:

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList();

        if (n <= 0) {
            ret.add(0);
            return ret;
        }

        ret.add(0);
        ret.add(1);

        int sz = -1;
        for (int i = 2; i <= n; ++i) {
            sz = ret.size();

            for (int j = sz - 1; j >= 0; --j) {
                ret.add(ret.get(j));
            }

            for (int j = sz, len = sz * 2; j < sz; ++j) {
                ret.set(j, ret.get(j) & (1 << (i - 1)));
            }
        }
        return ret;
    }
}

Summary

LeetCode Gray Code: By recursive definition (backtracking’s angle), gray code (n bits) = 0 1 +gray code (n-1 bits), and it could be done in a iterative way.
Written on May 26, 2013