Sort Integers in an array by the number of 1 Bits in each integer

Question

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the sorted array.

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

So, I used Brian Kernigham's Algorithm here to count the number of 1 bits in each integer present in the array. This is what I've coded so far :-

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        //firstly sort the input array
        sort(arr.begin(), arr.end());
        
        
        vector<int> count;
        //Using Brian Kernigham's Algorithm
        for(int i =0; i<arr.size(); i++){
            while(arr[i]){
                arr[i] = arr[i] & (arr[i] -1);
                count[i] ++;
            }
        } 
    }
};

But, I don't know how to combine the count[] array and the input array, arr[] to get the output. I thought of using map() STL of C++ but since the function needs to return vector<int>, I dropped the thought of it.

Can somebody provide the further solution to it? Also, please don't share any code which uses the pre-defined function builtin_popcount()

Answer 1

The simplest (but not most efficient) is to store the numbers and the counts together in a container, sort that, and the extract the numbers:

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<std::pair<int,int> temp;
        
        for(int i =0; i<arr.size(); i++){
            int count = 0;
            while(arr[i]){
                arr[i] = arr[i] & (arr[i] -1);
                count++;
            }
            temp.emplace_back(count,arr[i]);
        } 
       
        std::sort(temp.begin(),temp.end());   

        // extract the numbers again:
        std::vector<int> numbers;
        // ...
        return numbers;
    }
};

std::sort is not stable, so if you first sort the numbers and then sort again for the number of set bits, you would have to use std::stable_sort. On the other hand, std::pair<int,int> does have a operator< that can be used with std::sort to sort according to first and then second.

Alternatively you could write a comparator that lets you sort the numbers. This will not have all the unnecessary copying like the above, but it will call the function to count the bits more than necessary:

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
       std::sort(arr.begin(), arr.end(), [](int a,int b) {
               // count bits here
               auto n_bits_a = count_bits(a);
               auto n_bits_b = count_bits(b);
               if (n_bits_a == n_bits_b) return a < b;
               return n_bits_a < n_bits_b; });
        return arr;
    }
};

The comparator can be written more compact if again we use the fact that std::pair<int,int> already has the desired ordering:

std::sort(arr.begin(), arr.end(), [](int a,int b) {
    auto proj = [](int x) { return std::pair<int,int>{ count_bits(x),x}; };
    return proj(a) < proj(b);
});  

It is not completely clear, why the function takes the vector by reference and returns a vector. The above also sorts the parameter.