Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Gray Code

Problem Statement
The gray code is a binary numeral system where two successive values differ in only one bit. Given an integer n representing 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 - 1

Example 2

Input: n = 3

Output: [0,1,3,2,6,7,5,4]

Solution

class Solution:
    def grayCode(self, n: int) -> List[int]:
        x = [0,1]
        if n == 1:
            return [0, 1]
        
        y = 1
        count = 1
        result = []
        while count < n:
            mask = 1 << y
            for i in x[::-1]:
                x.append(i | mask)
            y+=1
            count+=1
        return x