# XxOoRr Solution | XXOORR | CODECHEF JULY CHALLENGE

Share:

View problem on codechef

Given an array A1,A2…ANA1,A2…AN, find the minimum number of operations (possibly zero) required to convert all integers in AA to 00.

In one operation, you

• choose a non-negative integer pp (p≥0p≥0),
• select at most KK indices in the array AA, and
• for each selected index ii, replace AiAi with Ai⊕2pAi⊕2p. Here, ⊕⊕ denotes bitwise XOR.

### Input

• The first line contains an integer TT – the number of test cases. Then TT test cases follow.
• The first line of each test case contains two integers NN, KK – the size of the array and the maximum number of elements you can select in an operation.
• The second line of each test case contains NN integers A1,A2…ANA1,A2…AN.

### Output

For each test case, output the minimum number of operations to make all elements of the array 00.

### Constraints

• 1≤T≤1051≤T≤105
• 1≤N,K≤1051≤N,K≤105
• 0≤Ai≤1090≤Ai≤109
• The sum of NN over all test cases does not exceed 2⋅1052⋅105

• Subtask #1 (100 points): Original Constraints

### Sample Input

``````1
3 2
3 6 10
``````

### Sample Output

``````5
``````

### Explanation

Here is one way to achieve [0,0,0][0,0,0] from [3,6,10][3,6,10] in 55 operations:

1. Choose p=0p=0 and indices {1}{1}. Now AA becomes [2,6,10][2,6,10].
2. Choose p=1p=1 and indices {1,2}{1,2}. Now AA becomes [0,4,10][0,4,10].
3. Choose p=1p=1 and indices {3}{3}. Now AA becomes [0,4,8][0,4,8].
4. Choose p=2p=2 and indices {2}{2}. Now AA becomes [0,0,8][0,0,8].
5. Choose p=3p=3 and indices {3}{3}. Now AA becomes [0,0,0][0,0,0].

It can be shown that at least 55 operations are required.

## SOLUTION

``````Join telegram channel for updates

#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long int nt;
void solve (vector<nt> &r,nt n)
{
string s="";
nt i,j=31;
while(n>0)
{
s+=to_string(n%2);
n/=2;
}
nt n1=s.size();
for(i=0;i<n1;i++)
{
if(s[i]=='1')
{
r[j]+=1;
}

j--;
}

}
int main()
{
nt t,i,j;
cin>>t;
while(t--)
{
nt n,k;
cin>>n>>k;
vector<int> a(n);
for(i=0;i<n;i++)
cin>>a[i];

vector<nt> r(32,0);
for(i=0;i<n;i++)
{
solve(r,a[i]);
}
nt ans=0;
for(i=0;i<32;i++)
{
if(r[i]==0)
continue;
else if(r[i]%k==0)
{
ans+=(r[i]/k);
}
else
{
ans+=(r[i]/k+1);
}
}
cout<<ans<<"\n";
}

return 0;
}``````