In this HackerEarth Monk's Choice of Numbers problem solution, Monk loves cakes! He visits the Binary Bakery to buy some of his favorite cheesecakes.

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.

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

Help Monk find the maximum number of cakes that he can have.

 

HackerEarth Monk's Choice of Numbers problem solution


HackerEarth Monk's Choice of Numbers problem solution.

#include<bits/stdc++.h>


using namespace std;

#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define CLEAR(array, value) memset(ptr, value, sizeof(array));
#define si(a)     scanf("%d", &a)
#define sl(a)     scanf("%lld", &a)
#define pi(a)     printf("%d", a)
#define pl(a)     printf("%lld", a)
#define pn        printf("\n")

int foo(int n)
{
  int count = 0;
  while(n)
  {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

int main()
{
  freopen("in.txt","r",stdin);
  freopen("out","w",stdout);
  ios_base::sync_with_stdio(0);
  int t;
  cin>>t;
  assert(1<=t && t<=10);
  while(t--)
  {
    int i,j,n,k;
    cin>>n>>k;
    assert(1<=n && n<=1000);
    assert(0<=k && k<=n);
    vector<int>v(n);
    rep(i,n)
    {
    cin>>v[i];
    assert(0<=v[i] && v[i]<=100000);
    }
    vector<int>bt(n);
    rep(i,n)
    bt[i]=foo(v[i]);
    sort(bt.rbegin(),bt.rend());
    int ans=0;
    for(i=0;i<k;i++)
      ans+=bt[i];
    cout<<ans;
    if(t>0)cout<<"\n";
  }
return 0;
}

Second solution

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

int main()
{
    ios_base::sync_with_stdio(0); 
    int T; cin >> T;
    assert (1<=T and T<=10); 
    for (int g=0; g<T; g++){
        int N, K; cin >> N >> K;
        assert (1<=N and N<=1000); 
        assert (0<=K and K<=N); vector <int> t; 
        for (int y=1; y<=N; y++){
            int x; cin >> x; 
            assert (0<=x and x<=100000); 
            t.push_back(__builtin_popcount(x));
        }
        sort(t.begin(), t.end());reverse(t.begin(),t.end());
        int ans = 0; 
        for (int y=0;y<K; y++) ans+=t[y]; cout << ans << '\n';
    }
    return 0;
}