XxOoRr | CodeChef Solution

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

Task

Given an array A₁, A₂ . . . A_N, 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 A_i with A_i⊕2^p. 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 A₁, A₂ . . . A_N.

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 ≤ A_i ≤ 10⁹
• The sum of N 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:

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
	{
		// your code goes here
		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.