# Gray Code

#### Given a number â€˜grayNumberâ€™. Find the gray code sequence.

#### Conditions for a gray code sequence :

```
1. Gray code sequence contains numbers from 0 to 2^'grayNumber'-1 in bit/binary form.
2. Two consecutive gray code sequence numbers only differ by 1 bit.
3. Gray code sequence must start with 0.
```

#### Example :

```
Given 'grayNumber' : 2.
```

```
As depicted from above image, the gray code sequence is 0,1,3,2.
```

#### Note :

```
1. The output sequence must contain the decimal representation of numbers instead of the binary form.
2. There can be multiple answers print anyone.
```

##### Input format :

```
The first line of input contains an integer â€˜Tâ€™ denoting the number of test cases.
The first line of every test case contains an integer â€˜grayNumberâ€™.
```

##### Output Format :

```
For each test case, return the â€˜list/vectorâ€™ of the Gray code sequence.
The output is â€˜Validâ€™ if returned gray code sequence is correct. Else â€˜Invalidâ€™.
```

##### Note :

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 2
0 <= grayNumber <= 15
Time Limit : 1 sec
```

Suppose are finding an answer for â€˜Nâ€™ size but we have already the solution for â€˜N-1â€™. then use the previous answer for a new answer. (where â€˜Nâ€™ is â€˜grayNumberâ€™)

- Letâ€™s consider â€˜N' : 3 and we have solution of â€˜N-1' : 2 : { â€˜00â€™, â€˜01â€™, â€˜10â€™, â€˜11â€™} and called it â€˜PREâ€™.
- Create a new list/vector of â€˜PREâ€™ in reverse order { â€˜11â€™, â€˜10â€™, â€˜01â€™, â€˜00â€™ } called it â€˜NEWâ€™.
- Add â€˜0â€™ as a prefix, in all the elements of â€˜PREâ€™ : { â€˜000â€™, â€˜001â€™, â€˜010â€™, â€˜011â€™ } /
- Add â€˜1â€™ as a prefix, in all the elements of â€˜NEWâ€™ : { â€˜111â€™, â€˜110â€™, â€˜101â€™, â€˜100â€™} .
- Concatenate the â€˜PREâ€™ + â€˜NEWâ€™ and it will be answered for â€˜N' : 3.
- Return a number conversion of new concatenated â€˜list/vectorâ€™.

The approach is to recursively add the 0 and 1 each time until the number of bits is not â€˜N' (where â€˜Nâ€™ is â€˜grayNumberâ€™)

Here is the algorithm :

- Base case : If â€˜Nâ€™ is equal to 0.
- Return { â€˜0â€™ }.

- If â€˜N' is equal to 1
- Return { â€˜0â€™, â€˜1â€™ }.

- Call a function SOLVE(grayNumber),
- Then it returns all gray code sequence from 0 to 2^'grayNumber'-1 calls it â€˜ANSWERâ€™ list/vector.
- Now generate a gray code sequence for 'grayNumber' + 1
- Add 0 in all the elements of â€˜ANSWERâ€™ as a prefix, and called it â€˜PREâ€™.
- Add â€˜1â€™ in all the elements of â€˜ANSWERâ€™ in reverse order, as a prefix, and called it â€˜NEWâ€™.
- Return concatenated â€˜PREâ€™+â€™NEWâ€™.

Suppose the current answer for 'N' : 2 is : {0, 1, 3, 2} (where â€˜Nâ€™ is â€˜grayNumberâ€™ ) then add 2*2 in all the elements in reverse order : { 2+4, 3+4, 1+4, 0+4} then our answer for 'N' : 3 will be : {0, 1, 3, 2, 6, 7, 5, 4}.

Why this is working?

Convert {0, 1, 3, 2} in binary bits form {'00', '01', '11', â€˜11â€™} it is the answer for â€˜Nâ€™ : 2 if we add '0' as prefix and '1' as a prefix in reverse order of binary representation then we get an answer for 'N' : 3. { â€˜0â€™+â€˜00â€™, â€˜0â€™+â€™01â€™, â€˜0â€™+â€˜10â€™, â€˜0â€™+â€™11â€™) by adding '0' as the prefix, (â€˜1â€™+â€˜11â€™, â€˜1â€™+â€™10â€™, â€˜1â€™+â€˜01â€™, â€˜1â€™+â€™00â€™) by adding '1' as the prefix in reverse order }.

You can observe in adding â€˜0â€™ part we are doing nothing because â€˜0â€™ canâ€™t make any change in the number, and adding â€˜1â€™ part is increasing the value of all the elements in reverse order by 2^'N'.

Here is the algorithm :

- Create a list/vector (say, â€˜DPâ€™) to store the answer of size 2^'grayNumber'.
- â€˜DPâ€™[1] =1.
- Run a loop from 2 to 2^'grayNumber-1â€™ (say, iterator â€˜iâ€™)
- Update â€˜DPâ€™[i] as â€˜DPâ€™[i-c] + â€˜POWERâ€™
- â€˜POWERâ€™ is a small nearest 2â€™s power of â€˜iâ€™.
- â€˜Câ€™ is reverse iterator will run option direction of â€˜iâ€™

- Finally, return â€˜DPâ€™.

Since we need only 1 bit change, we can use XOR with 1 bit shifts. With the use of this property and XOR we can generate numbers which differ by 1 bit. Operation : â€˜iâ€™ ^ ( 'i' >> 1 ) gives the gray code for â€˜iâ€™th number.

Example :

Given â€˜N' : 3 ( where â€˜Nâ€™ is â€˜grayNumberâ€™) and let iterator be â€˜iâ€™ which iterates from 0 to 2^3 - 1 (7).

Iteration 0 : â€˜iâ€™ = 0, â€˜iâ€™ ^ ( â€˜iâ€™ >> 1 ) = 0 ^ 0 = 0 {000}

Iteration 1 : â€˜iâ€™ = 1, â€˜iâ€™ ^ ( 'i' >> 1 ) = 1 ^ 0 = 1 {001}

Iteration 2 : â€˜iâ€™ = 2, â€˜iâ€™ ^ ( 'i' >> 1 ) = 2 ^ 1 = 3 {011}

Iteration 3 : â€˜iâ€™ = 3, â€˜iâ€™ ^ ( 'i' >> 1 ) = 3 ^ 1 = 2 {010}

Iteration 4 : â€˜iâ€™ = 4, â€˜iâ€™ ^ ( 'i' >> 1 ) = 4 ^ 2 = 6 {110}

Iteration 5 : â€˜iâ€™ = 5, â€˜iâ€™ ^ ( 'i' >> 1 ) = 5 ^ 2 = 7 {111}

Iteration 6 : â€˜iâ€™ = 6, â€˜iâ€™ ^ ( 'i' >> 1 ) = 6 ^ 3 = 5 {101}

Iteration 7 : â€˜iâ€™ = 7, â€˜iâ€™ ^ ( 'i' >> 1 ) = 7 ^ 3 = 4 {100}

All the numbers generated differ by 1 bit.

Here is the algorithm :

- Create an array (say, â€˜ANSWERâ€™) which will store the numbers.
- Run a loop from 0 to 2^'grayNumber' (say, iterator â€˜iâ€™)
- Create a variable (say, â€˜VALâ€™) which will denote as the current number to added in the â€˜ANSWERâ€™.
- Update â€˜VALâ€™ to ( â€˜iâ€™ ^ ('i' >> 1)).
- Insert â€˜VALâ€™ in â€˜ANSWERâ€™.
- Finally, return â€˜ANSWERâ€™.