[LeetCode]89. Gray Code(Medium)
1 min readMar 19, 2021
Description:
The gray code is a binary numeral system where two successive values differ in only one bit.
Given an integer
nrepresenting the total number of bits in the code, return any sequence of gray code.A gray code sequence must begin with
0.
Example 1:
Input: n = 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
[0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1Solution 1:
Time complexity O(2^n). Each time we need to add 1 to the head of the numbers in binary. And the sequence starts from the tail of result List.
Input: n = 1
Explanation:
0 - 0
------
1 - 1Input: n = 2
Explanation:
00 - 0
01 - 1
-------
11 - 3
10 - 2Input: n = 3
Explanation:
000 - 0
001 - 1
011 - 3
010 - 2
--------
110 - 6
111 - 7
101 - 5
100 - 4