Codechef July Challenge 2021 Solution | XXOORR | TechTalkBot


Codechef July Challenge 2021 Solution | XXOORR | TechTalkBot


Codechef July Challenge 2021 Solution | XXOORR | TechTalkBot

Table of Contents

By TechTalkBot


Task

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

In one operation, you

  • choose a non-negative integer p (p ≥ 0),
  • select at most K indices in the array A, and
  • for each selected index i, replace Ai with Ai⊕2p. Here, ⊕ denotes bitwise XOR.

Input

  • The first line contains an integer T – the number of test cases. Then T test cases follow.
  • The first line of each test case contains two integers NK – 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 N integers A1, A2 . . . AN.

Output

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

Constraints

  • 1 ≤ T ≤ 105
  • 1 ≤ NK ≤ 105
  • 0 ≤ Ai ≤ 109
  • The sum of N over all test cases does not exceed 2⋅105

Subtasks

  • 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] from [3,6,10] in 5 operations:

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

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

Solution – XxOoRr

Solution:-

Sample Input

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
int ans;
int n,k,count;
while(t--)
{

cin>>n>>k;
vector<int> a(n);
for(int& i : a)
{
cin>>i;
}
vector<int> nSetBits(31);
int count;
int term;

for(int bit = 0 ; bit <= 30 ; bit++)
{
count = 0;
for(int&i : a)
{
if(i%2!=0)
{
count++;
}
i=i/2;
}
nSetBits[bit] = count;
}
ans=0;
for(int bit=0; bit<=30 ; bit++)
{

if(nSetBits[bit]%k==0)
{
ans=ans+nSetBits[bit]/k;
}
else
{
ans = ans + nSetBits[bit]/k+1;
}
}
cout<<ans<<endl;
}


return 0;
}



Conclusion:

Keep Reading
Thank You


If you are interested in Google Analytics Academy Certification
Check out this-