Monk’s Choice of Numbers

QUESTION

The owner of the bakery, Bob, is a clever man. He does not want Monk to finish all his cheesecakes. Hence, he plays a game.\n\nThe Monk is given N numbers and has to select K of these numbers. For each number that Monk chooses, he will get as many cheesecakes as the number of 1’s in the Binary representation of the number i.e. the number of bits that are set.\n\nHelp Monk find the maximum number of cakes that he can have.\n\nInput:\n\nThe first line of input contains T. T test cases follow.\nFirst line of each test cases contains 2 space-separated integers N and K.\nThe next line contains N space-separated integers.\n\nOutput:\nFor each test cases, print the answer in a new line.\n\nConstraints:\n1<= T <= 10\n1 <= N <= 10^3\n0 <= K <= N\n0 <= Numbers <= 10^5.

ANSWER

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define si(a)     cin>>a //scanf("%d", &a)
#define sl(a)     cin>>b //scanf("%lld", &a)
#define pi(a)     cout<<a //printf("%d", a)
#define pl(a)     cout<<a //printf("%lld", a)
#define pm(str)   cout<<str //printf("%s\n",str)
#define pn        cout<<"\n" //printf("\n")

ll counter(ll n){
	ll count = 0;
	while(n){
		n = n & (n-1);
		count++;
	}
	return count;
}
int main(){
	vector<ll> v;
	int t;
	si(t);
	while(t--){
		int n,k;
		v.clear();
		scanf("%d %d",&n,&k);
		v.resize(n);
		for(int i = 0;i < n;i++){
			int t;
			si(t);
			v[i] = counter(t) ;
		}
		sort(v.begin(),v.end());
		int j = n-1;
		ll sum = 0;
		for(int i = 0;i < k;i++){
			sum += v[j];
			j--;
		}
		pl(sum);
		pn;
	}
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.