Permutation Xority solution codechef

SOLUTION – CLICK HERE

You are given an integer NN. Construct a permutation AA of length NN which is attractive.

A permutation is called attractive if the bitwise XOR of all absolute differences of adjacent pairs of elements is equal to 00.

Formally, a permutation A=[A1,A2,…,AN]A=[A1,A2,…,AN] of length NN is said to be attractive if:

where ⊕⊕ denotes the bitwise XOR operation.

Output any attractive permutation of length NN. If no attractive permutation exists, print −1−1 instead.

Note: A permutation of length NN is an array A=[A1,A2,…,AN]A=[A1,A2,…,AN] such that every integer from 11 to NN occurs exactly once in AA. For example, [1,2,3][1,2,3] and [2,3,1][2,3,1] are permutations of length 33, but [1,2,1][1,2,1], [4,1,2][4,1,2], and [2,3,1,4][2,3,1,4] are not.

Input Format Permutation Xority solution codechef

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of a single line of input, containing one integer NN.

Output Format

For each test case, output on a single line an attractive permutation of NN integers, or −1−1 if no attractive permutation exists.

Permutation Xority solution codechef Constraints

• 1≤T≤10001≤T≤1000
• 2≤N≤1052≤N≤105
• Sum of NN over all cases won’t exceed 2⋅1052⋅105.

Sample Input 1 

2
3
6

Sample Output 1 

3 2 1
5 2 3 6 4 1 

Explanation Permutation Xority solution codechef

Test Case 11: |3−2|⊕|2−1|=1⊕1=0|3−2|⊕|2−1|=1⊕1=0

Note that there are other correct answers — for example, [1,2,3][1,2,3] would also be accepted as correct.

Test Case 22: |5−2|⊕|2−3|⊕|3−6|⊕|6−4|⊕|4−1|=3⊕1⊕3⊕2⊕3=0

SOLUTION – CLICK HERE