XxOoRr (XXOORR) Solution — Codechef July Long Challenge

  • 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

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

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

--

--

--

Software Developer ,currently pursuing B.Tech in Information Technology. Electronic Dance Music is love.Also like all phone related technologies

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Rovi Weekly Update #1

Greatest GSA SER VPS

Auto-Diagnosis and Remediation in Netflix Data Platform

An Ultimate Guide to Stratos Decentralized Storage

Exploring user behavior in Android with Google Analytics for Firebase

10 Kafka Best Practices

Start your on-demand service business using the Taskrabbit clone script

Scalability — Monolith to Microservices

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Anubhav Mishra

Anubhav Mishra

Software Developer ,currently pursuing B.Tech in Information Technology. Electronic Dance Music is love.Also like all phone related technologies

More from Medium

The Differences Between Static and Dynamic Libraries.

Salient points of Linked Lists in 3 mins

Become a master at maintaining and auditing your database

Class and Object