Last Updated: 10 Mar, 2021

Circular Permutation In Binary Representation

Moderate

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.
Return the ans array.

Solve now