Backtracking     Bit Manipulation     Math     Medium    

Problem Statement:

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

  • Every integer is in the inclusive range [0, 2n - 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]

 

Constraints:

  • 1 <= n <= 16

Solution:

We see the pattern:

1: [0,1]
2: [00,01,11,10]
3: [000,001,011,010,110,111,101,100]

Notice the following recursive relation:

grayCode(n) = [grayCode(n-1), new_part]

new_part consists of 1 added to the left of each item in reversed sequence of grayCode(n-1).

This leads us to the following code:

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n==1: return [0,1]
        prev = self.grayCode(n-1)
        return prev + [2**(n-1)+i for i in prev[::-1]]

Time complexity: O(n).