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