Sort Integers by The Number of 1 Bits . I used one sort function to sort the vector ? But why sort is not working?

Question

Sort Integers by The Number of 1 Bits

Leetcode : Problem Link

Example Testcase :

Example 1:

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]\

Example 2:

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.

My Solution :

class Solution {
public:
unsigned int setBit(unsigned int n){
    unsigned int count = 0;
    while(n){
        count += n & 1;
        n >>= 1;
    }
    return count;
}
vector<int> sortByBits(vector<int>& arr) {
    map<int,vector<int>>mp;
    for(auto it:arr){
        mp[setBit(it)].push_back(it);
    }
    for(auto it:mp){
        vector<int>vec;
        vec=it.second;
        sort(vec.begin(),vec.end()); //This Sort Function of vector is not working
    }
    vector<int>ans;
    for(auto it:mp){
        for(auto ele:it.second){
            ans.push_back(ele);
        }
    }
    return ans;
}
};

In my code why sort function is not working ?

[1024,512,256,128,64,32,16,8,4,2,1]

For the above testcase output is [1024,512,256,128,64,32,16,8,4,2,1] because of sort function is not working. It's correct output is [1,2,4,8,16,32,64,128,256,512,1024]

Note : In the above example testcase every elements of the testcase has only one set-bit(1)

Answer 1

As your iteration in //This sort function ... refers to mp as the copy of the value inside the map, sort function will not sort the vector inside it, but the copy of it. Which does not affecting the original vector<int> inside the mp. Therefore, no effect occurs. You should refer the vector inside the map as a reference like this:

class Solution {
public:
    unsigned int setBit(unsigned int n) {
        unsigned int count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    vector<int> sortByBits(vector<int>& arr) {
        map<int, vector<int>>mp;
        for (auto it : arr) {
            mp[setBit(it)].push_back(it);
        }
        for (auto& it : mp) {
            sort(it.second.begin(), it.second.end()); //Now the sort function works
        }
        vector<int>ans;
        for (auto it : mp) {
            for (auto ele : it.second) {
                ans.push_back(ele);
            }
        }
        return ans;
    }
};

Although there is more design problem inside your solution, this will be a solution with minimized modification.

Answer 2

vector<int>vec is a copy of a copy of the one in the map which is then discarded. Try:

for(auto& entry:mp){
    vector<int>&vec=entry.second;
    sort(vec.begin(),vec.end());
}

Your other for loops should also use references for efficiency but it won't affect the behaviour.

Answer 3

Here is memory efficient and fast solution. I don't know why you are using map and extra vector. we can solve this questions without any extra memory efficiently. We just have to make a Comparator function which will sort elements according to our own requirements. Please let me know in comments if you require further help in code (or if you find difficult to understand my code). I am using __builtin_popcount() function which will return me number of set bits in a number.

bool sortBits(const int a, const int b){ //Comparator function to sort elements according to number of set bits
    int numOfBits1 = __builtin_popcount(a);
    int numOfBits2 = __builtin_popcount(b);
    if(numOfBits1 == numOfBits2){ //if number of set bits are same, then sorting the elements according to magnitude of element (greater/smaller element)
        return a < b;
    }
    return (numOfBits1 < numOfBits2); //if number of set bits are not same, then sorting the elements according to number of set bits in element
}
class Solution {
public:

vector<int> sortByBits(vector<int>& arr) {
    sort(arr.begin(),arr.end(), sortBits);
    return arr;
}
};

Answer 4

I assume the OP is just learning, so fiddling with various data structures etc. can carry some educational value. Still, only one of the comments pointed out that the starting approach to the problem is wrong, and the whole point of the exercise is to find a custom method of comparing the numbers, by number of bits first, then - by value.

Provided std::sort is allowed (OP uses it), I guess the whole solution comes down to, conceptually, sth likes this (but I haven't verified it against LeetCode):

template <typename T>
struct Comp
{
    std::size_t countBits(T number) const
    {
        size_t count;
        while(number) {
            count += number & 1;
            number>>=1;
        }
        return count;
    }
    
    bool operator()(T lhs, T rhs) const
    {
        /*
        auto lb{countBits(lhs)};
        auto rb{countBits(rhs)};
        return lb==rb ? lhs < rhs : lb < rb;
        * The code above is the manual implementation of the line below
        * that utilizes the standard library
        */
        return std::tuple{countBits(lhs), lhs} < std::tuple{countBits(rhs), rhs};
    }
};


class Solution {
public:
    void sortByBits(vector<int>& arr) {
        std::sort(begin(arr), end(arr), Comp<int>{});
    }
};

Probably it can improved even further, but I'd take it as starting point for analysis.

Answer 5

The problem is already evaluated and the fix is aready explained.

I want to give 2 additional/alternative solution proposals.

• In C++17 we have the std::bitset count function. Please see here
• And in C++20 we have directly the std::popcount function. Please see here.

(Elderly and grey haired people like me would also find 5 additional most efficient solutions in the Book "Hackers Delight")

Both variants lead to a one statement solution using std::sort with a lambda.

Please see:

#include <algorithm>
#include <vector>
#include <iostream>
#include <bitset>

// Solution
class Solution {
public:
    std::vector<int> sortByBits(std::vector<int>& arr) {
        std::sort(arr.begin(), arr.end(), [](const unsigned int i1, const unsigned int i2)
            { size_t c1{ std::bitset<14>(i1).count() }, c2{ std::bitset<14>(i2).count() }; return c1 == c2 ? i1 < i2 : c1 < c2; });
            //{ int c1=std::popcount(i1), c2=std::popcount(i2); return c1 == c2 ? i1 < i2 : c1 < c2; });
        return arr;
    }
};

// Test
int main() {
    std::vector<std::vector<int>> testData{
        {0,1,2,3,4,5,6,7,8},
        {1024,512,256,128,64,32,16,8,4,2,1}
    };

    Solution s;
    for (std::vector<int>& test : testData) {
        for (const int i : s.sortByBits(test)) std::cout << i << ' ';
        std::cout << '\n';
    }
}