Hail XOR Codechef Solution

Today we will be looking into a competitive programming question. That is, the Hail XOR Codechef solution. Coders also name it as HXOR Problem and codechef asked this question as a part of their December Challenge 2020 problem. 

Thus, learning this problem will help you clear your concepts about XOR. Additionally, this problem could add up to your list of important questions for competitive programming. 

Hence, without much delay, let’s get our coding brains to use and get started!

Prerequisites to solving the Hail XOR Problem:

For the Hail XOR problem, you need to know how XOR operation works. To understand that, go through the explanation below. 

We define XOR as  exclusive or for two integers. For instance, a and b.

To find XOR, we first find the binary representation of both a and b.

Let us understand it better by an example. Suppose a = 7 and b = 10.

So binary representation of a = 111 and b = 1010.

Now, if we add 0 before integers it remains the same, this applies to binary representation also. Since binary representation of a contains less bits than b we write a as 0111 because adding 0 before doesn’t make any difference.

Now XOR of a and b will be : 

a       = 0 1 1 1

b       = 1 0 1 0

XOR= 1 1 0 1

i.e we find XOR for each corresponding bits.

Rules of XOR:

First lets see the rules for XOR

1. If both bits are 1 then XOR’ed bit will be 0.

2. And, if both bits are 0 then XOR’ed bit will be 0.

3. If one bit is 0 and one bit is 1 XOR’ed bit will be 1.

In the above example, we find XORed bit for each corresponding pair of bits.

(First Bit Pair) 0 XOR 1 = 1 (Rule 3)

(Second Bit Pair) 1 XOR 0 = 1 (Rule 3)

(Third Bit Pair) 1 XOR 1  = 0 (Rule 1)

(Fourth Bit Pair) 1 XOR 0 = 1 (Rule 3)

So, finally we get a XOR b as 1101.

To find XOR of more than two numbers, we represent all numbers in binary representation, add 0’s before if necessary and write like this.

0 1 1 1 0

0 1 1 0 1

1 0 0 1 0

and so on.

To find each bit of XOR just calculate the number of 1’s in the corresponding bits. If it is even or zero then that XOR’ed bit is 0. If it is odd then that XOR’ed bit is 1.

For the above example.

(First corresponding bits) 0 XOR 0 XOR 1 = 1

(Second corresponding bits) 1 XOR 1 XOR 0 = 0

(Third corresponding bits) 1 XOR 1 XOR 0 = 0

(Fourth corresponding bits) 1 XOR 0 XOR 1 = 0

(Fifth corresponding bits) 0 XOR 1 XOR 0 = 1

So, final XOR will be 10001.

Additionally, In all languages you can XOR two integers say a and b by ‘^’ this operation.

i.e to find a XOR b, just do a^b.

Some more rules related to XOR.

  • a^a = 0
  • 0^a = a

Problem Statement:

You are given a sequence A1,A2,…,AN and you have to perform the following operation exactly X times:

Choose two integers i and j such that 1≤i<j≤N.

Choose a non-negative integer p.

Change Ai to Ai⊕2p, and change Aj to Aj⊕2p, where ⊕ denotes bitwise XOR.

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

A sequence B1,B2,…,BN is said to be lexicographically smaller than a sequence C1,C2,…,CN if there is an index i such that Bi<Ci and for each valid j<i, Bj=Cj.

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 A1,A2,…,AN.

Output

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

Constraints

1≤T≤10

2≤N≤105

1≤X≤109

1≤Ai≤109 for each valid i

Subtasks

Subtask #1 (30 points): N≤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 (2,2,3). Consider the following three operations:

Choose i=1, j=2 and p=1. Then, A1 changes from 2 to 2⊕21=0 and similarly, A2 changes from 2 to 2⊕21=0. Now the sequence is (0,0,3).

Next, choose i=1, j=2 and p=1. Then, A1 changes to 0⊕21=2 and A2 changes to 0⊕21=2. The sequence is (2,2,3).

Next, again choose i=1, j=2 and p=1. Then, A1 changes to 2⊕21=0 and A2 changes to 2⊕21=0. The sequence is (0,0,3) again.

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

Hail XOR Codechef Solution:

Approach:

We can implement the hail xor problem once our approach is clear. Hence, let us go through some observations and the procedure on how we will implement the problem.

At first we observe that, to obtain the optimal solution, we need to take a particular power of 2. So that the number doesn’t toggle to reduce drastically when we XOR it. 

Thus, in order to achieve that, we conclude to a condition, largest 2p n. Which means we take the largest power less than the most significant bit. 

Then, we will reduce the leftmost elements before proceeding to the right elements.

We will take two iteration variables i and j. We take i for the largest power of 2. And j will traverse from i+1 to n.

And for every A[j] we are going to XOR with largest power of 2 and check if it gives the smallest number. If it does, then we will replace and if not, we will move to the next j.

Finally, if we traverse and replace all the elements and still remaining operations are odd and n is 2 , we will XOR the last two elements with 1.

Program:

#include <bits/stdc++.h>
using namespace std;
#define int long long int 
vector<int > setbitPosition(int n){
    vector<int > v;
    int i=0;
    while(n!=0){
        if(n&1==1){
            v.push_back(i);

        }
        n=(n>>1);
        i++;
    }
    return v;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int mod=1000000007;
    int t;
    cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        vector<int > v(n+1);
        v[0]=0;
        for(int i=1;i<=n;i++){
            int k;
            cin>>k;
            v[i]=k;
        }
       // vector<int >setbit=setbitPosition(6);
       int j=2;
         int operation=0;
       for(int i=1;i<n;i++){
           if(x==0){
               break;
           }
           int c=v[i];

           vector<int >setbit=setbitPosition(c);
         
           for(int l=setbit.size()-1;l>=0;l--){
               if(x==0){
               break;
           }
               int p=setbit[l];
               p=1<<p;
               v[i]=v[i]^p;
               int j=0;
               for(j=i+1;j<=n;j++){
                   int curr=v[j];
                   if((curr^p)<curr){
                       v[j]=curr^p;
                       break;
                   }
               }
               if(j==n+1){
                   v[n]=v[n]^p;

               }
               //operation++;
               x--;
           }

       }
       // for(int i=1;i<=n;i++){
         //  cout<<v[i]<<" ";
      // }
      // cout<<endl;
      /// x=x-operation;
       if(x>0){
            if(x%2!=0&&n==2){
                v[1]=1;
                v[2]=v[2]^1;
      }
       
      }
       for(int i=1;i<=n;i++){
           cout<<v[i]<<" ";
       }
       cout<<endl;
   
          }
  return 0;  
}

Hail XOR Codechef Solution Explanation:

Even after studying the code, you might face some difficulties. Hence, let us go through a detailed explanation of the program. 

First and foremost, be clear that you need to iterate n times and not x times which can be a confusion. So, we iterate through the first array. 

Then, we will try to reduce ith element as small as possible in a single operation. As said earlier, we will reduce the element by taking  2p where p will be most significant bit.

Thus, we will reduce ith element a[i] XOR 2p and for jth element we will iterate from i+1 element to n.

And if we find any element which is gives a smaller result when XORed with the number above, we choose the same element and reduce a[j]=a[j] XOR 2p.

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

Note that we will not increment i until a[i] becomes zero or total operation becomes zero.

For the next iteration, we search for the next most significant bit and repeat the same steps until a[i] is 0.

Lastly, for the most significant bit, we have written a function which returns all set bit position in the curr or current element. After we reach the position n-1, the result will have some operations left. Then, we achieve the same sequence if n is not equal to 2.

There is also a special case which was defined earlier. Where we have one operation left and n is 2. In that case,

if(remaining 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.

Ending note:

Hail XOR is an easy-medium problem for the Codechef challenge. Thus, you can perform it easily if you solve for 1 test case and general approach. Once you have achieved that, you can code the rest without difficulty. 

Additionally, HAIL XOR Codechef solution will boost your confidence in competitive programming. Also, it will help you practice for your next codechef challenge. It is also helpful for other coding challenges. Therefore, make sure to practice and understand the question and its solution properly.

Still have doubts or queries? Just ask away. We are here to help.

See you in our next post!

Read Mashmokh and ACM Editorial here

Leave a Comment

Your email address will not be published. Required fields are marked *