# Circular Permutation In Binary Representation

#### You are given the two integers 'N' and 'X'. Your task is to find an array 'P' such that:

```
'P' is a permutation of (0, 1, 2, ..., 2 ^ (N - 1)).
The first element of the array 'P' is 'X', i.e., P[0] = X.
Adjacent elements of 'P' (i.e., P[i] and P[i + 1]) differ by only 1 bit in their binary representation.
The first and the last element (i.e., P[0] and P[2^N -1]) are also considered as adjacent elements.
```

##### Note:

```
For N = 2, [0,1,2,3], [0,2,3,1], [1,2,3,0] are some of the valid permutations but [0,0,1,2], [1,2,3,4], [1,1,1,3] are not.
It is guaranteed that an array 'P' always exits with the given requirements.
```

##### Input Format:

```
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.
The first line and only line of each test case contain 2 positive integers, 'N' and 'X', as described in the problem statement.
```

##### Output Format:

```
For each test case, print in a new line an array 'P' of size 2^N denoting a permutation of (0,1, ..., 2^N -1) with the given requirements, as described in the problem statement.
If there exist multiple permutations satisfying the above conditions, then you can print any.
Output for each test case will be printed in a separate line.
```

##### Note:

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

##### Constraints:

```
1 <= T <= 100
1 <= N <= 13
0 <= X < 2^N
Time Limit: 1 sec
```

The idea here is to use an algorithm to generate **n**-bit **gray code**. Recall that, n-bit gray code sequence is a sequence of **2^n** numbers from **0** to **2^n -1** such that it starts with **0** and two successive values differ only in 1 bit. Let say this sequence to be **arrGray**. More information on how to generate n-bit gray code can be found here: Wikipedia.

We have to find the index of **X** (which is given in the problem) in sequence **arrGray**. Let say we have found **X** at the **i**-th index of **arrGray**. Then simply, our required array **P** can be **arrGray**[**i**:] + **arrGray**[:**i**], which means **P **is the **Concatenation** of the two subarrays of **arrGray**. The first one is from **i**-th index to the last, and the second, from the **0**-th index to the **(i-1)**th index.

**Steps:**

- Call the function
**grayCode**passing**N**as an argument that returns an array. Let it be**arrGray**of size 2^**N**consisting of the n-bit gray code sequence. - Create a variable of data type int named
**ind**to store the index of the**X**in the**arrGray**. - Run a loop from
**i**=**0**to the**size**of**arrGray**and do:- If
**arrGray[i]**==**X**, then set**ind**to**i**and**break**the loop.

- If
- Create an array
**ans**to store the answer. - Run a loop from
**i**=**ind**to the**size**of**arrGray**:- Add
**arrGray[i]**to the array**ans**.

- Add
- Now, run a loop from
**i**=**0**to**ind**:- Add
**arrGray[i]**to the array**ans**.

- Add
- Return the array
**ans**.

**int [] grayCode(int n):**

- Create an
**array**of data type int named as**ans**to store the final n-bit gray code sequence. - Also, create an
**array**of data type string named**temp**as we are using the binary representation in the form of the string and at last convert these into the int. - Add the 1-bit pattern into the temp so that the
**temp**will become {**“0”,”1”**}. - Run a loop with a variable
**i**from**2**to**pow**(2,n), and after each iteration, change**i**=**i**<< 1:- Run a loop from
**j**=**i-1**to**0**inclusive:- Add
**temp[j]**to the array**temp**.

- Add
- Run a loop to access the
**1st**half of the array**temp**, i.e., run a loop from**j**= 0 to**i**and do:**temp[j]**= “0” +**temp[j]**

- Similarly, run a loop from
**j**=**i**to 2***i**and do:**temp[j]**= “1” +**temp[j]**

- Run a loop from
- Run a loop to convert elements of the array
**temp**, denoting binary representation into the**int**and adding the same to the array**ans**. - Return the array
**ans**.

This approach is based on the XOR method to generate an n-bit gray code sequence. For each **i** in [0, pow(2, N) -1], the **i**-th index of the sequence will be** i ⊕ (i >> 1)**. As 1st number in the sequence will be 0 and if we substitute **i **= 0, then **i ⊕ (i >> 1) **= 0. For **i** = 1, we get **i ⊕ (i >> 1) **= 1 and for **i** = 2 it will be 3 and so on. More information on how to use XOR for the gray code generation can be found here: CP-Algorithms.

Now, we can use the same logic to construct the new array, which can start from the given number **X **by using the **Concatenation** of the two subarrays **arrGray**[**i**:] and **arrGray**[:**i**], where **arrGray** is the sequence of n-bit gray code, and **i** is the index of **X** in that sequence. Or if we do further **observation**, we can arrive at the following equation to directly generate the sequence that is starting from the given number **X**, that is, for each **i** in [0, pow(2, N) -1], the **i**-th index of the sequence will be** X ⊕ (i ⊕ (i>>1))**.

**Steps:**

- Create an empty array
**ans**of data types int to store the required sequence. - Run a loop with a variable
**i**from**0**to**pow**(2,**N**) and in each iteration do:- Add
**X ⊕ (i ⊕ (i>>1))**to the array**ans**.

- Add
- Return the
**ans**array.