Permutation Xority codechef solution- 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:

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:

|A1A2||A2A3||AN1AN|=0|A1−A2|⊕|A2−A3|⊕…⊕|AN−1−AN|=0

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

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • Sum of NN over all cases won’t exceed 21052⋅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: |32||21|=11=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: |52||23||36||64||41|=31323=0

SOLUTION – CLICK HERE

Leave a Comment

Your email address will not be published.