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.

**Understand of the problem:**

The problem asks for outputting all Gray Code. For the background knowledge about the gray code, please refer the link

http://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81#.E4.BA.8C.E9.80.B2.E4.BD.8D.E6.95.B8.E8.BD.89.E6.A0.BC.E9.9B.B7.E7.A2.BC

For n = 1's Gray Code:

0

---

1

For n = 2 Gray Code:

00

01

-----

11

10

For n = 3 Gray Code:

000

001

011

010

----------

110

111

101

100

So we can see that for the Gray code sequence with n, it equals to (n - 1)'s Gray code sequence, as shown in the upper half the examples. The below halves are equal to the sum of n- 1 gray code plus the 1 << (n - 1), in backward order.

**Code (Java):**

public class Solution { public List<Integer> grayCode(int n) { List<Integer> result = new ArrayList<Integer>(); if (n == 0) { result.add(0); return result; } List<Integer> lastGray = grayCode(n - 1); int addOnNum = 1 << (n - 1); result.addAll(lastGray); for (int i = lastGray.size() - 1; i >= 0; i--) { result.add(lastGray.get(i) + addOnNum); } return result; } }

## No comments:

## Post a Comment