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

Advanced Python made easy

link Command in Linux

Huawei App Multipler in Action!

How to Get Started With Common Data Environment (CDE) for BIM

All About Modularity and Scale (Software Stack @ Zenatix, Part-3)

A beginner’s guide to creating desktop applications using Electron

LAMBDA SCHOOL — WEEK 5: BUILD WEEK

Version 1.3 of Visual Studio Template OnionAPI Now Available

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

Working with Java development IDE

Save Water and Electricity with IoT-based Alert System

What is the Epoch Time?

Why Java is platform independent