XxOoRr - Codechef July Long Challenge Solution in C++ | AskTheCode

Codechef July Long Challenge 2021 Solution | XxOoRr (XXOORR) in C++ | AskTheCode

---

Problem:

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 p (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 N integers A1,A2…AN.
  

Output:

For each test case, output the minimum number of operations to make all elements of the array 0.

---

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.

---

Code:

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt", "w", stdout);
	#endif
	    void calc(vector<int> &v, int N);
		int test;
		cin >> test;
		while (test--){
		    int N, K;
		    cin >> N >> K;
		    int arr[N];
		    for(int i=0; i<(int)N; i++)
		        cin >> arr[i];
		    vector<int> v(32, 0);
		    for (int i=0; i<N; i++)
		        calc(v, arr[i]);
		    
		    int result = 0;
		    for (int i=0; i<32; i++){
		        if (v[i] == 0)
		            continue;
		        else if (v[i] % K == 0)
		            result += (v[i] / K);
		        else
		            result += (v[i] / K + 1);
		    }
		    cout << result << endl;
		}
	return 0;
}

void calc(vector<int> &v, int N){
    string str="";
    int i, j=31;
    while(N > 0){
        str += to_string(N%2);
        N /= 2;
    }
    int size = str.size();
    for (i=0; i<size; i++){
        if (str[i] == '1')
            v[j] += 1;
        j--;
    }
}