89. Gray Code

Problem Description

An n-bit gray code sequence is a sequence of 2n integers where:

• Every integer is in the inclusive range [0, 2^n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Solution

First, let’s check out what is a “Gray Code”, https://www.wikiwand.com/en/Gray_code

A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a “reflected” code, or more specifically still, the binary reflected Gray code.

Initially, I dont have any thoughts on this problem. I think up a “DFS” solution with tremendous sanity check, until I met this video solution

Below are the solution from the video, I just paraphased into text format.

we can start from Gray Code with only one number

0

then how about two numbers? n == 1

0
1

When n == 2, we have four numbers in the Gray Code array: (0, 1, 2, 3),
in order to create the grayCode(2), we can do the following steps:

- we mirror the grayCode(1)
- add `1` to the left most bits, 


- step 1: mirror the grayCode(1)

0
1
--
1
0


step 2: add `1` to the leftmost bits of the mirrored numbers

during this step, since adding `0` to left most bits does not affect the number,
so this step actually does two sub-steps:

1. add `0` to grayCode(1)'s leftmost bits
2. add `1` to mirrored numbers' leftmost bits

00
01
--
11
10

^^ this is the result of grayCode(2)


apply the same rule to grayCode(3):


0 00
0 01
0 11
0 10
---
1 10
1 11
1 01
1 00

^^ this is the result of grayCode(3)

Python

class Solution:
    def grayCode(self, n: int) -> List[int]:
        gray_code = [0]
        if n == 0:
            return gray_code

        for i in range(n):
            length = len(gray_code)
            for j in range(length - 1, -1, -1):
                gray_code.append( gray_code[j] | (1 << i) )

        return gray_code

Java

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

        if (n == 0)
            return grayCode;

        for (int i = 0; i < n; i++) {
            int length = grayCode.size();
            for (int j = length - 1; j >= 0; j--) {
                grayCode.add(grayCode.get(j) | (1 << i) );
            }
        }

        return grayCode;
    }
}

Complexity Analysis

• Time Complexity:
  • 1 + 2 + 4 + 8 + ….. + 2^n = 2^n - 1
• Space Complexity:
  • O(1)
    • the arrayList is the result we need to return, besides that, we only create scalar variables