XxOoRr Solution | XXOORR | CODECHEF JULY CHALLENGE

Codechef

View problem on codechef

Given an array A1,A2…ANA1,A2…AN, find the minimum number of operations (possibly zero) required to convert all integers in AA to 00.

In one operation, you

  • choose a non-negative integer pp (p≥0p≥0),
  • select at most KK indices in the array AA, and
  • for each selected index ii, replace AiAi with Ai⊕2pAi⊕2p. Here, ⊕⊕ denotes bitwise XOR.
For the work from home Internship Programs : Click here to apply now

Input

  • The first line contains an integer TT – the number of test cases. Then TT test cases follow.
  • The first line of each test case contains two integers NN, KK – 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…ANA1,A2…AN.

Output

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

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤N,K≤1051≤N,K≤105
  • 0≤Ai≤1090≤Ai≤109
  • The sum of NN over all test cases does not exceed 2⋅1052⋅105

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][0,0,0] from [3,6,10][3,6,10] in 55 operations:

  1. Choose p=0p=0 and indices {1}{1}. Now AA becomes [2,6,10][2,6,10].
  2. Choose p=1p=1 and indices {1,2}{1,2}. Now AA becomes [0,4,10][0,4,10].
  3. Choose p=1p=1 and indices {3}{3}. Now AA becomes [0,4,8][0,4,8].
  4. Choose p=2p=2 and indices {2}{2}. Now AA becomes [0,0,8][0,0,8].
  5. Choose p=3p=3 and indices {3}{3}. Now AA becomes [0,0,0][0,0,0].

It can be shown that at least 55 operations are required.

SOLUTION

Join telegram channel for updates
Please click 1-2 ads on this website to support us

#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long int nt;
void solve (vector<nt> &r,nt n)
{
    string s="";
    nt i,j=31;
    while(n>0)
    {
        s+=to_string(n%2);
        n/=2;
    }
        nt n1=s.size();
        for(i=0;i<n1;i++)
        {
            if(s[i]=='1')
            {
                r[j]+=1;
            }
            
            j--;
        }
        
    
}
int main()
{
    nt t,i,j;
    cin>>t;
    while(t--)
    {
        nt n,k;
        cin>>n>>k;
        vector<int> a(n);
        for(i=0;i<n;i++)
        cin>>a[i];
        
        vector<nt> r(32,0);
        for(i=0;i<n;i++)
        {
            solve(r,a[i]);
        }
        nt ans=0;
        for(i=0;i<32;i++)
        {
            if(r[i]==0)
            continue;
            else if(r[i]%k==0)
            {
                ans+=(r[i]/k);
            }
            else
            {
                ans+=(r[i]/k+1);
            }
        }
        cout<<ans<<"\n";
    }

    return 0;
}

Read more post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x