Monk and Tasks : HackerEarth 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 the ith day is the number of ones in the binary representation of Arrayi.

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 on each day. Help him out!



Input:

The first line of input contains an integer T, where T is the number of test cases.
The first line of each test case contains N, where N is the number of days.
The second line of each test case contains Array array having N elements, where Arrayi represents the number of tasks provided by Monk D to Monk A on ith day.

Output:

Print all the tasks provided to Monk A in the non-decreasing order of number of tasks performed by him.

Constraints:

1 <= T <= 100
1 <= N <= 105
1 <= Arrayi <= 1018

Note:
If two numbers have the same number of ones (set bits), print the one which came first in the input first, and then the other one, as in the input.

Sample Input

1
4
3 4 7 10

Sample Output 

4 3 10 7

Explanation

In the sample input, T = 1 and N = 4, where N is the number of days.

Tasks provided to Monk A on first day is 3 and binary representation of 3 is { 11 }2, which contains 2 ones.

Tasks provided to Monk A on second day is 4 and binary representation of 4 is { 100 }2, which contains 1 ones.

Tasks provided to Monk A on third day is 7 and binary representation of 7 is { 111 }2, which contains 3 ones.

Tasks provided to Monk A on fourth day is 10 and binary representation of 10 is { 1010 }2, which contains 2 ones.

So the Output will be: 4 3 10 7

C Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
int tobinary(int N)
{
 int count=0;
 while(N)
 {
  if(N&1)
  count++;
  N>>=1;
 }
 return count;
}

int main()
{
    int T,N,*a,hash[MAX],i,ones,*b,temp,j;
    scanf("%d",&T);
    a=(int*)malloc(sizeof(int)*100);
    b=(int*)malloc(sizeof(int)*100);
    while(T--)
    {
     scanf("%d",&N);
     i=0;
     memset(hash,0,sizeof(hash));
     for(i=0;i<N;i++)
     {
      scanf("%d",*(a+i));
      ones=tobinary(*(a+i));
      hash[*(a+i)]=ones;
      *(b+i)=ones;
     }
     for(i=0;i<N;i++)
     {
      for(j=i+1;j<N;j++)
      {
       if(*(b+i)>*(b+j))
       {
        temp=*(b+i);
        *(b+i)=*(b+j);
        *(b+j)=temp;
       }
      }
     }
     for(i=0;i<N;i++)
     {
      for(j=0;j<N;j++)
      {
       if(hash[*(a+j)]==*(b+i))
       {
        printf("%d",*(a+j));
        hash[*(a+j)]=0;
       }
      }
     }
    }
    return 0;
}

Java Implementation:

import java.util.*;
import java.lang.*;
import java.io.*;

class TestClass {
 public static int countOnes(int n)
 {
  int count=0;
  while(n>0)
  {
   if((n&1) == 1)
    count++;
   n>>=1;
  }
  return count;
 }
 
 public static void sortOnes(int a[],int ones[],int n)
 {
  for(int i=0;i<n-1;i++)
  {
   for(int j=i+1;j<n;j++)
   {
    if(ones[a[i]]>ones[a[j]])
    {
     int temp = a[i];
     a[i] = a[j];
     a[j] = temp;
    }
   }
  }
 }
 
 public static void printArray(int a[],int n)
 {
  for(int i=0;i<n;i++)
   System.out.print(a[i] + " ");
 }
 
    public static void main(String args[] ) throws Exception {
        Scanner in = new Scanner(System.in);
  int t = in.nextInt();
  int ones[] = new int[1000];
  //Arrays.fill(ones,0);
  while(t>0)
  {
   int n = in.nextInt();
   int a[] = new int[n];
   for(int i=0;i<n;i++)
   {
    a[i] = in.nextInt();
    if(ones[a[i]]==0)
     ones[a[i]]=countOnes(a[i]);
   }
   
   //sort array a[] based on array ones[]
   sortOnes(a,ones,n);
   printArray(a,n);
   t--;
  }
 }
}