Circular Permutation In Binary Representation

'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.

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.

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.

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.

N-bit gray code

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.
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.
Now, run a loop from i = 0 to ind:
- Add arrGray[i] to the array ans.
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.
- 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 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.

Time Complexity

O(2 ^ N), where N is the positive number given in the problem.

We are creating an n-bit Gray code sequence whose size is 2 ^ N. So, we have to run a loop till 2 ^ N for the sequence. Hence, the overall time complexity is O(2 ^ N).

Space Complexity

O(2 ^ N), where N is the positive number given in the problem.

We are using an array of size 2 ^ N for storing both the n-bit gray code sequence and the final answer. Hence, the space complexity is O(2 ^ N).

Circular Permutation In Binary Representation

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Output 1:

Sample Input 2:

Sample Output 2:

Steps:

int [] grayCode(int n):