# XxOoRr | CodeChef Solution

Hello coders, today we are going to solve XxOoRr CodeChef Solution whose Problem Code is XXOORR.

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 N, K – 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 â‰¤ N, K â‰¤ 105
• 0 â‰¤ Ai â‰¤ 109
• The sum of N over all test cases does not exceed 2â‹…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] from [3,6,10] in 5 operations:

1. Choose p = 0 and indices { 1 }. Now A becomes [2, 6, 10].
2. Choose p = 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

### C++

```#include<bits/stdc++.h>
#include<vector>

using namespace std;

int main()
{
int t,ans,n,k;
cin>>t;
while(t--)
{
cin>>n>>k;
vector<int> a(n);
for(int& i:a){
cin>>i;
}
vector<int> nbit(31);
int c,t1,i;
for(int j=0; j<=30; j++){
c=0;
for(int& i:a){
if(i%2!=0){
c++;
}
i/=2;
}
nbit[j]=c;
}
ans =0;
for(int j=0; j<=30; j++){
if(nbit[j]%k==0){
ans+=nbit[j]/k;
}
else{
ans +=nbit[j]/k+1;
}
}
cout<<ans<<"\n";
}
return 0;
}```

### Python

```from math import *
for j  in range(int(input())):
n,k = map(int,input().split())
arr = list(map(int,input().split()))
bitarr = [0]*(32)
for i in range(32):
for item in arr:
if item&(1<<i):
bitarr[i]+=1
total = 0
for item in bitarr:
total+=ceil(item/k)
print(total)```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n,k;
n = sc.nextInt();
k = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
int x = sc.nextInt();
arr[i] = x;
}
int sum[] = new int[33];
for(int i=0;i<n;i++){
int x = arr[i];
int j = 32;
while(x>0){
sum[j]+=x%2;
j--;
x=x/2;
}
}
int c=0;
for(int i=0;i<33;i++){
if(sum[i]%k==0){
c+= sum[i]/k;
}else{
c+= sum[i]/k;
c+=1;
}
}
System.out.println(c);
}
}
}
```

Disclaimer: The above Problem (XxOoRr) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.