# XxOoRr (XXOORR) Solution — Codechef July Long Challenge

**Problem Statement**

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 pp (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 NN 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≤10⁵
- 1≤N,K≤10⁵
- 0≤Ai≤10⁹
- The sum of NN over all test cases does not exceed 2⋅10⁵

# 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:

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

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

**Code (Solution)**

The code has been implemented in 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

{

// your code goes here

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

while(t-->0){

int n = sc.nextInt();

int k = sc.nextInt();

int arr[] = new int[n];

for(int i=0;i<n;i++){

arr[i] = sc.nextInt();

} 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 /= 2;

}

}

int cnt=0;

for(int i=0;i<33;i++){

if(sum[i]%k==0){

cnt+= sum[i]/k;

}else{

cnt+= sum[i]/k;

cnt+=1;

}

}

System.out.println(cnt);

}

}

}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

**References**

(Video Editorial Link For Better Explanation)