## Hail XOR December codechef challenge problem solution 2020-

You are given a sequence and you have to perform the following operation exactly times:

- Choose two integers and such that .
- Choose a non-negative integer .
- Change to , and change to , where denotes bitwise XOR.

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

A sequence is said to be lexicographically smaller than a sequence if there is an index such that and for each valid , .

### Input

- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains two space-separated integers and .
- The second line contains space-separated integers .

### Output

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

### Constraints

- for each valid

### Subtasks

Subtask #1 (30 points):

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 . Consider the following three operations:

- Choose , and . Then, changes from to and similarly, changes from to . Now the sequence is .
- Next, choose , and . Then, changes to and changes to . The sequence is .
- Next, again choose , and . Then, changes to and changes to . The sequence is 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.

## Comments

## Post a Comment