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:

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].

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

Contest Page | CodeChef

(Video Editorial Link For Better Explanation)