In this HackerEarth Monk and Tasks problem solution, Monk A loves to complete all his tasks just before the deadlines for introducing unwanted thrill in his life. But, there is another Monk D who hates this habit of Monk A and thinks it's risky.

To test Monk A, Monk D provided him tasks for N days in the form of an array Array, where the elements of the array represent the number of tasks.

The number of tasks performed by Monk A on an ith day is the number of ones in the binary representation of Array.

Monk A is fed up of Monk D, so to irritate him even more, he decides to print the tasks provided in non-decreasing order of the tasks performed by him each day. Help him out!



HackerEarth Monk and Tasks problem solution


HackerEarth Monk and Tasks problem solution.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1000005;
ll Ar[MAX];
vector <ll> vec[80];
//counting number of ones in binary representation.
ll count_one(ll a)
{
    ll coun=0;
    while(a>0)
    {
        coun++;
        a = a&(a-1);
    }
    return coun;
}
int main()
{

    int t;
    for(cin>>t;t;--t)
    {
        ll n;
        cin>>n;
        ll maxi=-1;
        for(int i=0;i<=70;i++)
        vec[i].clear();
        for(int i=0;i<n;i++)
        {
          cin>>Ar[i];
          ll num_one = count_one(Ar[i]);
           vec[num_one].push_back(Ar[i]);
           if(num_one > maxi)
           maxi=num_one;
        }
        for(int i=0;i<=maxi;i++)
        {
            for(int j=0;j<vec[i].size();j++)
            {
                if(i == maxi and j==vec[i].size()-1)
                {
                    cout<<vec[i][j]<<endl;
                }
                else
                {
                    cout<<vec[i][j]<<" ";
                }
            }
        }

    }
       return 0;
}

Second solution

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

const int MAX = 1e5 + 5;
pair <int, pair<int, long long> > p[MAX];

int main() {
    int t, n, x;
    long long a, b;
    cin >> t;
    assert(1<= t and t <= 100);
    while(t--) {
        cin >> n;
        assert(1 <= n and n <= 100000);
        for(int i = 0; i<n; ++i) {
            cin >> a;
            assert(1 <= a and a <= 1000000000000000000LL);
            x = 0;
            b = a;
            while(b)
                x += (b & 1), b >>= 1;
            p[i] = make_pair(x, make_pair(i, a));
        }
        sort(p, p + n);
        for(int i = 0;i < n;++i)
            cout << p[i].second.second << ' ';
        cout << endl;
    }
    return 0;
}