The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:


Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1


Example 2:


Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

Difficulty: interview

Starter code:

class Solution:
    def grayCode(self, n: int) -> List[int]:
        

Solutions:
class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         res = []
         for i in range(1<<n):
             res.append(i ^ i >>1)
         return res


class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
               
         result = [0, 1]
         if n <= 1:
             return result[:n+1]
         res_len = 2 ** n
         
         cnt = 1
         while len(result) != res_len:
             cnt *= 2
             result.extend(result[::-1])
             #offset = 0 
             start = len(result) // 2
             for i in range(start, len(result)):
                 #if i > 0 and i % cnt == 0:
                 #    offset = cnt;
                 #result[i] += offset 
                 result[i] += cnt
             
         return result

class Solution:
     def grayCode(self, n):
         
         if n == 0:
             return [0]
         
         concat = ''
         
         res = [0, 1]
         
         for i in range(1, n):
             newRes = []
             
             for j in res:
                 newRes.append(j)
             for j in reversed(res):
                 newRes.append(j + (2 ** i))
                 
             res = newRes
             
         return res
             
             
         
         """
         :type n: int
         :rtype: List[int]
         """


class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         if n == 0:
             return [0]
         result = [0, 1]
         
         # mirror the previous layer
         # then padding '1' at the most significant bit position --- for the second half
         # 0 1  --> 00 01 | 11 10 (1 + 1; 1 + 0)
         
         for i in range(2, n + 1):
             mask = 1 << (i - 1)
             temp = []
             for j in range(len(result)):
                 temp.append(result[-j - 1] | mask)
             result += temp
         return result
         


class Solution:
     def helper(self, n):
         if n == 0:
             return ['0']
         if n == 1:
             return ['0', '1']
         ret = []
         for code in self.helper(n - 1):
             ret.append('0' + code)
         for code in reversed(self.helper(n - 1)):
             ret.append('1' + code)
         return ret
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         if n == 0:
             return [0]
         ret = []
         code = self.grayCode(n - 1)
         ret += code
         for v in reversed(code):
             ret.append(2 ** (n - 1) + v)
         return ret
         


class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         result = [0]
         for i in range(n):
             temp = [] 
             for num in result:
                 temp.append(num + 2**i)
             result += temp[::-1]
             
         return result


class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         if n == 0:
             return [0]
     
         q = [0, -1]
     
         for i in range(n):
             tag = 0
             while q[0] != -1:
                 item = q.pop(0)
                 q.append(item * 2 + tag)
                 q.append(item * 2 + (1 - tag))
                 tag = 1 - tag
             q.pop(0)
             q.append(-1)
     
         q.pop(-1)
         
         return q

class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
               
         result = [0, 1]
         if n <= 1:
             return result[:n+1]
         res_len = 2 ** n
         
         cnt = 1
         while len(result) != res_len:
             cnt *= 2
             #orig_len = len(result)
             for i in range(cnt - 1, -1, -1):
                 result.append(result[i] + cnt)
             
         return result

class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         
         if n < 0:
             return []
         elif n == 0:
             return [0]
         elif n == 1:
             return [0, 1]
         
         result = [0, 1]
         res_len = 2 ** n
         
         cnt = 1
         while len(result) != res_len:
             cnt *= 2
             result.extend(result[::-1])
             offset = 0 
             for i in range(len(result)):
                 if i > 0 and i % cnt == 0:
                     offset = cnt;
                 result[i] += offset
             
             
         return result
         
         


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


class Solution:
     # @return a list of integers
     def grayCode(self, n):
         res=[]
         size=1<<n
         for i in range(size):
             res.append((i>>1)^i)
         return res

class Solution:
     def grayCode(self, n):
         """
         :type n: int
         :rtype: List[int]
         """
         ans = [0]
         mask = 0x1
         for l in range(n):
             for c in ans[::-1]: 
                 ans.append(mask | c)
             mask <<= 1    
         return ans