Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit.

For example 2-bit gray code is shown below.

00

01

11

10

Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray code is explained below. An n-bit gray code can be generated from (n-1) bit gray code as follows.

1-bit gray code is obvious; it is 0,1.

2-bit gray code can be generated as follows.

- Expand the sequence by adding it's elements in reverse order (in this case 1, 0).
- Prepend zeros to the first half and Ones to the second Half

**0**0

**0**1

-----

**1**1

**1**0

3-bit gray code can be generated similarly.

**0**00

**0**01

**0**11

**0**10

------

**1**10

**1**11

**1**01

**1**00

Below is the implementation of this algorithm in C++.