Last Updated: 10 Nov, 2020
Sort An Array According To The Count Of Set Bits
Moderate
Asked in companies
You are given an array consisting of N positive integers, and your task is to sort the array in decreasing order of count of set bits in the binary representation of the integers present in the array.
In other words, you have to modify the array such that an integer with more number of set bits should appear before the integer which has lesser number of set bits in its binary representation.
The number of set bits is nothing but the number of 1s present in the binary representation of the integer. For example, the number of set bits in 5(0101) is equal to 2.
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
Approaches
- 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.
- Make use of comparator function while calling the inbuilt sort function (Comparator functions are the functions that forms the basis of the comparison based sorting approach).
- Design the comparator function as follows:
Comparator(int num1, int num2):
If (countofsetbits(num1)>countofsetbits(num2))
Return true;
Else
Return false;
- This function compares the count of set bits in the numbers and it returns true if the count of set bits is greater in the first number else it returns false because the order of sort is descending.
- The count of set bits for any integer can be found using plenty of methods. One of the easiest methods is to keep dividing the number by two unless it becomes 0, and at each stage, if the remainder is 1, then increment the count.
- Maintain an array of vectors( vector<datatype>name[size]) of size 33( Because here we are considering that each element of the input array is of max 32 bits).
- Now traverse all the elements of the array and count the number of set bits for each element. Suppose the count of set bits is ‘cnt’, then push this element in the vector at index ‘cnt’ of the array.
- Clear the input vector to use it as the answer vector.
- Now traverse the array of vectors from the end (because we need the answer to be sorted in descending order of set bits count), and if the size of the vector at the index being traversed is greater than 0, then push the values of this vector in the same order into the answer vector( Input Vector)
Similar problems