Reference: LeetCode EPI 15.11

Difficulty: Medium

My Post: Java Solutions with Detailed Comments and Explanations (Backtracking, Prepending)

## 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:**

1 | Input: 2 |

## 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`

.

1 | private boolean isValid(int n1, int n2) { |

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`

.

1 | public List<Integer> grayCode(int n) { |

**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`

.

1 | n = 0, we have [0]. |

**Note:** Consider the corner cases when `n = 0`

and `n = 1`

, and then decide `i`

should start from $0$.

1 | public List<Integer> grayCode(int n) { |

**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):**

1 | public List<Integer> grayCode(int n) { |

Same complexity.