# Leetcode: Gray Code

Gray Code

Similar Problems:

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.

```For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

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

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/gray-code
class Solution:
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
res = [0]
for i in range(n):
v = pow(2, i)
for j in range(len(res)-1, -1, -1):
res.append(res[j]+v)
return res

## Basic Ideas: dynamic programming
##  get f(n) from f(n-1)
##      copy the original
##      add pow(2, n-1) to each item from right to left
##
##   from f(2) to f(3)
##      00 01 11 10
##      00 01 11 10 110 111 101 100
## Complexity:
def grayCode_v1(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n <= 0: return [0]
if n == 1: return [0, 1]
import copy
l = [0, 1]
for i in range(2, n+1):
l2 = copy.deepcopy(l)
v = pow(2, i-1)
for k in range(len(l)-1, -1, -1):
l2.append(v+l[k])
l = l2
return l

# s = Solution()
# print(s.grayCode(2))
# print(s.grayCode(3))
```

Share It, If You Like It.