Positive AND Codehef October long challenge Solution |CodeChef October long challenge editorial

Positive AND codechef October long challenge Solution |Codechef October long challenge editorial -

This Problem is taken from Codechef  October long challenge and I have explained Positive and complete solution.

Problem Statement-

A permutation p1,p2...pN$p_1,p_2...p_N$ of {1,2,...,N}$\{1,2,...,N\}$ is beautiful if pi&pi+1$p_i\mathrm{\&}{p}_{i+1}$ is greater than 0 for every 1≤i<N$1\le i<N$ . You are given an integer N$N$, and your task is toconstruct a beautiful permutation of length N$N$ or determine that it's impossible.

Note that a&b$a\mathrm{\&}b$ denotes the bitwise AND of a$a$ and b$b$.

Input:

First-line will contain T$T$, number of testcases. Then the testcases follow. Each testcase contains a single line of input, an integer N$N$.

Output:

For each test case output −1$-1$ if there is no suitable permutation of length N$N$, otherwise output N$N$ integers in a single line which form a beautiful permutation. If there are multiple answers output any of them.

Constraints

• 1≤N≤105$1\le N\le {10}^5$
• The sum of N$N$ over all test cases does not exceed 106${10}^6$

Subtasks

• 50 points : 1≤N,T≤9$1\le N,T\le 9$
• 50 points : Original constraints

Sample Input:

3
4
3
5

Sample Output:

-1
1 3 2
2 3 1 5 4

 link of problem-https://www.codechef.com/OCT20B/problems/POSAND

Read More-Chef and Easy Queries CodeChef October long challenge problem solution editorial

read more-Covid Run Codechef October long challenge problem solution| Codechef October long challenge problem solution

read More-Replace for X codechef October long challenge solution | codechef October long challenge editorial

Solution-

Positive AND problem was little bit tricky problem.

mistake 1- Do not try to build the same output as given in custom input.

mistake 2- these can more then one ans of this problem so you can print any one of them.

lets jump to my approach

I was thinking while solving the problem what wrong with the given permutation why it is not valid solution.

so i got ans by the observation that when a 2^n(1,2,4,8,16....) number AND with 2^n-1(1,3,7,15) number it forms always zero because in 2^n number only MSB present(eg 2=10,4=100,8=1000) other bit are equals to zero.

So my assumed permutation can be valid answer if i swap 2^n number with there next elements. so that it can not form 0 while doing AND 

operation.

To make my permutation valid I have to swap these numbers with to number next to it. For eg. I will swap 8 to 9,16 to 17 ,32 to 33...

and print -1 if N is 2^n because in this case we cannot swap N to N+1 because we have no choice left.

So here is my working code.