-->

Hail XOR  December codechef challenge problem solution 2020-

Hail XOR problem is taken from December codechef challenge 2020. Let's read problem statement.

You are given a sequence ${A}_{1},{A}_{2},\dots ,{A}_{N}$ and you have to perform the following operation exactly $X$ times:

• Choose two integers $i$ and $j$ such that $1\le i.
• Choose a non-negative integer $p$.
• Change ${A}_{i}$ to ${A}_{i}\oplus {2}^{p}$, and change ${A}_{j}$ to ${A}_{j}\oplus {2}^{p}$, where $\oplus$ denotes bitwise XOR.

Find the lexicographically smallest sequence which can be obtained by performing this operation exactly $X$ times.

A sequence ${B}_{1},{B}_{2},\dots ,{B}_{N}$ is said to be lexicographically smaller than a sequence ${C}_{1},{C}_{2},\dots ,{C}_{N}$ if there is an index $i$ such that ${B}_{i}<{C}_{i}$ and for each valid $j${B}_{j}={C}_{j}$.

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains two space-separated integers $N$ and $X$.
• The second line contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$.

Output

For each test case, print a single line containing $N$ space-separated integers ― the lexicographically smallest obtainable sequence.

Constraints

• $1\le T\le 10$
• $2\le N\le {10}^{5}$
• $1\le X\le {10}^{9}$
• $1\le {A}_{i}\le {10}^{9}$ for each valid $i$

Subtask #1 (30 points): $N\le 100$

Subtask #2 (70 points): original constraints

Example Input

1
3 3
2 2 3


Example Output

0 0 3


Explanation

Example case 1: The original sequence is $\left(2,2,3\right)$. Consider the following three operations:

• Choose $i=1$$j=2$ and $p=1$. Then, ${A}_{1}$ changes from $2$ to $2\oplus {2}^{1}=0$ and similarly, ${A}_{2}$ changes from $2$ to $2\oplus {2}^{1}=0$. Now the sequence is $\left(0,0,3\right)$.
• Next, choose $i=1$$j=2$ and $p=1$. Then, ${A}_{1}$ changes to $0\oplus {2}^{1}=2$ and ${A}_{2}$ changes to $0\oplus {2}^{1}=2$. The sequence is $\left(2,2,3\right)$.
• Next, again choose $i=1$$j=2$ and $p=1$. Then, ${A}_{1}$ changes to $2\oplus {2}^{1}=0$ and ${A}_{2}$ changes to $2\oplus {2}^{1}=0$. The sequence is $\left(0,0,3\right)$ again.

We can check that after exactly 3 operations, this is the lexicographically smallest sequence we can obtain.

Solution -

hint- You have to iterate n time not x time.

Actually Hail XOR is easy-medium level question of this contest.You it's is pretty easy once you get 1 test case and general approach

to solve this question. As i told you in hint that you have to iterate n time not x time so we will first iterate through the array

and we will try to reduce ith element as small as possible in one operation. We can reduce current element 2^(msb) most significant bit.

so we will reduct ith elemet a[i] XOR 2^(msb) and for jth element we will iterate from i+1 elment to n and we found any element witch

gives smaller value when we do XOR this number with 2^msb we select that element and reduct a[j]=a[j] XOR 2^(msb)

if we do not find such element we will choose last element as jth element.

we will not increment i until a[i] become zero or total operation become zero.

in next time we will search for next msb of ith element. and reapeat same process until a[i] become zero.

for msb i have written a function which return all set bit position in curr element.

after i reach to n-1 ans still some operation left we can achive same squence if n is not equal to 2.

Special case-

if(remainng operation is odd and n==2){

if(x>0){

if(x%2!=0&&n==2){

v[1]=1;

v[2]=v[2]^1;

}

}

}

finally we print the array.

Here is my solution.

Join Telegram Channel for More Editorial.