Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integernrepresenting the total number of bits in the code, find the sequence of gray code. A gray code sequence must begin with0and with cover all 2^n integers.

Notice

For a givenn, a gray code sequence is not uniquely defined.

[0,2,3,1]is also a valid gray code sequence according to the above definition.

Example

Givenn = 2, return[0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Solution

• When n == 1, code sequence is 0, 1
• When n == 2, code sequence is 00, 01, 11, 10 (remove the first digit: 0, 1, 1, 0)
• When n == 3, code sequence is 000, 001, 011, 010, 110, 111, 101, 100 (remove the first digit: 00, 01, 11, 10, 10, 11, 01, 00)
• For n == i, since each code has one more bit than that of n == i - 1, we can add 0 ahead of each code in the code sequence of n == i - 1, and then reverse the code sequence of n == i - 1, and then add 1 ahead of each code in the reversed code sequence. Combined will be the code sequence for n == i.

public class Solution {
    /*
     * @param n: a number
     * @return: Gray code
     */
    public List<Integer> grayCode(int n) {

        List<Integer> result = new ArrayList<>();

        if (n < 0) {
            return result;
        }

        result.add(0);

        for (int i = 0; i < n; i++) {

            int previousSize = result.size();

            for (int j = previousSize - 1; j >= 0; j--) {

                result.add(result.get(j) | 1 << i);
            }
        }

        return result;
    }
}

Time complexity O(2 ^ n)

i = 0 -> j from 0 to 0 ---1 time

i = 1 -> j from 0 to 2^1 - 1 ---2^1 times

i = 2 -> j from 0 to 2^2 - 1 ---2^2 times

...

i = n -> j from 0 to 2^n - 1 ---2^n times

So the total number of loop time is 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n + 1) - 1