Searching and Sorting: Sort Integers by The Number of 1 Bits

Problem Statement:

You are given a array.
You have to sort the integers in ascending order by the number of 1’s in their binary format.

Example

Input: arr[] = {1, 2, 3, 4, 5, 6};
Output: 3 5 6 1 2 4
Explanation:
3 – 0011
5 – 0101
6 – 0110
1 – 0001
2 – 0010
4 – 0100
Hence the ascending order of number of 1’s are {3, 5, 6, 1, 2, 4}

Solution

The solution is very simple.
you need to create a custom comparator to check the count the number of set bits.
Then call a sorting function to sort the array.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

 static bool cmp(const int a, const int b) 
 {
     bitset<16> b1(a);
     bitset<16> b2(b);

     if(b1.count() == b2.count()) 
     {
         return a <= b;
     }
     return b1.count() < b2.count();
 }
 
 vector<int> sort_by_bits(vector<int>& arr) 
 {
     sort(arr.begin(), arr.end(), cmp);
     return arr;
 }

int main()
{
  vector<int> nums; 
    nums.push_back(1); 
    nums.push_back(2); 
    nums.push_back(3); 
    nums.push_back(4); 
    nums.push_back(5); 

   sort_by_bits(nums); 


    cout << "\nSorted array is = "; 
    for (int i = 0; i < nums.size(); i++) 
        cout << nums[i] << " "; 

    return 0;
}

Output:

Sorted array is = 1 2 4 3 5