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.