# Sort An Array According To The Count Of Set Bits

Posted: 10 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note :

``````1. If any two numbers have the same count of set bits, then in the sorted array they will appear in the order in which they appear in the original array. For example, let the array be { 2, 4, 3}, in this case, both 2 and 4 have the same number of set bits so the answer will be {3, 2, 4} and not {3, 4, 2}, because in the original array 2 appears before 4.

2. The array may contain duplicate elements.
``````
##### Input Format :
``````The first line of input contains the integer T, denoting the number of test cases.

The first line of each test case contains an integer N, denoting the size of the array.

The second line of each test case contains N space-separated integers denoting the array elements.
``````
##### Output Format :
``````The only line of output of each test case consists of N space-separated integers, the elements of the array in the order as described in the problem statement
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function. Also, you need to modify the given array in-place.
``````
##### Constraints :
``````1 <= T <= 50
1 <= N <= 10^4
1 <= arr[i] <= 10^9
`````` Approach 1
• Maintain a Multimap to store the pair of integer and its set bit count.
• The trick is to make (-1*count of set bits) as the key of the map because we have to sort the array on the basis of the count of set bits and it is multiplied by -1 because we have to sort it in descending order and by default the multimap store the integers in ascending order.
• Now traverse the map from the beginning and store all the elements in the array and return this array as the answer.