Medium

Quiz

#89 Gray Code

APPROACH

An n-bit Gray code sequence lists 2ⁿ integers from [0, 2ⁿ - 1] starting at 0, each appearing once, where every two consecutive entries (and the last and first) differ in exactly one binary bit. Given n, return any valid 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]

1 of 4

1:00

What is the optimal approach for this problem?