89. Gray Code

Description

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

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

Submitted Code

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]

Runtime: 7 ms | Beats 73.09%
Memory: 22.47 MB | Beats 77.10%

Gray Code 공식 i ^ (i >> 1) 을 이용하면 백트래킹보다 빠르게 풀 수 있다.

n = 2

i
0  →  00 ^ (00) = 00
1  →  01 ^ (00) = 01
2  →  10 ^ (01) = 11
3  →  11 ^ (01) = 10

res = [00,01,11,10]

Other Solutions

1st

class Solution:
    # @return a list of integers
    '''
    from up to down, then left to right
    
    0   1   11  110
            10  111
                101
                100
                
    start:      [0]
    i = 0:      [0, 1]
    i = 1:      [0, 1, 3, 2]
    i = 2:      [0, 1, 3, 2, 6, 7, 5, 4]
    '''
    def grayCode(self, n):
        results = [0]
        for i in range(n):
            results += [x + pow(2, i) for x in reversed(results)]
        return results

time complexity: 𝑂(2^𝑛)
space complexity: 𝑂(2^𝑛)

기존 Gray Code를 뒤집어서 맨 앞에 새로운 비트 1을 붙이는 반사(reflection) 방식이다.