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 of is beautiful if is greater than 0 for every . You are given an integer , and your task is toconstruct a beautiful permutation of length or determine that it's impossible.
Note that denotes the bitwise AND of and .
Input:
First-line will contain , number of testcases. Then the testcases follow. Each testcase contains a single line of input, an integer .
Output:
For each test case output if there is no suitable permutation of length , otherwise output integers in a single line which form a beautiful permutation. If there are multiple answers output any of them.
Constraints
- The sum of over all test cases does not exceed
Subtasks
- 50 points :
- 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
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.