89. Gray Code

Reference: LeetCode EPI 15.11
Difficulty: Medium

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.

Example:

Analysis

Backtracking

Instead of enumerating all possible permutations, which takes $O(2^{n\times 2^n})$, we construct the gray code by a step-by-step approach.

First, we design a function that checks if two numbers n1 and n2 differ only in one bit.

• n1 == n2: xor == 0, returns false.
• Differ in more than one bit: (xor & (xor - 1)) != 0, returns false.
• Differ in one bit: (xor & (xor - 1)) == 0, returns true.

Note: num & (num - 1) can remove the rightmost one-bit of num.

Consider we have a number 0110. How many differ-in-one numbers can we have for 0110? The answer is [1110, 0010, 0100, 0111]. We can write it out right away because we just need to do XOR operation for each bit. In other words, we XOR 0110 with [1000, 0100, 0010, 0001].

Based on this idea, we can take the latest generated number in the result list, and try out all differ-in-one possibilities. In order to know if the new candidate is qualified, we use a hash set to store all previously constructed numbers.

If the candidate is not in the hash set, we add it to the hash set and also append it to the result list. Then we construct the next number based on the number we’ve just added.

At last, when we have $2^n$ numbers in the result list, we need to check if the first and the last elements are compatible via isValid(n1, n2). If yes, everything is done; if no, backtrack and construct a new possible number, and try again.

Note: $2^i$ can be computed by 1 << i.

Time: $O(2^N)$ I don’t know how to get it~
Space: $O(2^N)$

Prepending 0 and 1

The idea is simple. Based on the result in n = k, we add $0$ before each element to get the first half; we add $1$ before each element of result and reverse the list to get the second half. Then concatenate them to get the result for n = k + 1. See the example below to understand it!.

Consider how we generate gray codes from n = 0 to n = 3.

Note: Consider the corner cases when n = 0 and n = 1, and then decide i should start from $0$.

Time: $O(2^N)$

• n = 0 ([0]), prepending “1” takes $1$ operation (allocating extra space takes $1$ operation and reversing takes $1$ operation, but they are proportional to number of prepending operations).
• n = 1 ([0, 1]), prepending “1” takes $2$ operations.
• n = 2 ([00, 01, 11, 10]), prepending “1” takes $4$ operations.
• n = 3 ([000, 001, 011, 010, 110, 111, 101, 100]), prepending “1” takes $8$ operations.
• n = k, prepending “1” takes $2^k$ operations.
• In total, $T(N) = 1 + 2 + 4 + 8 + \ldots + 2^N = 2^N$.

Space: $O(2^N)$

Without allocating extra space (In-Place):

Same complexity.

Comment
Junhao Wang
a software engineering cat