How to Sort Integers by The Number of 1 Bits?

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.

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.

Example 3:
Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:
Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:
Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Hints:
Simulate the problem. Count the number of 1’s in the binary representation of each integer.
Sort by the number of 1’s ascending and by the value in case of tie.

Count the Number of Set Bits

In order to solve the problem, we need to be able to count the number of ‘1’s in a number’s binary representation. A faster approach is detailed in here using the bit tweaks.

A classic approach using a loop would be:

1
2
3
4
5
6
7
8

int bitSet(int n) {
    int count = 0;
    while (n > 0) {
       count += (n & 1); // the rightmost bit
       n >>= 1;   //  shifting 1 to the right
    }
    return count;
}

int bitSet(int n) {
    int count = 0;
    while (n > 0) {
       count += (n & 1); // the rightmost bit
       n >>= 1;   //  shifting 1 to the right
    }
    return count;
}

In C++, we can use the built-in compiler intrinsic __builtin_popcount or the std::bitset class.

Sorting the Numbers using Custom Comparator

Then, we can just use std::sort() with a customize comparator. See below C++ implementations:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(begin(arr), end(arr), [](auto &a, auto &b) {
            int aa = __builtin_popcount(a);
            int bb = __builtin_popcount(b);
            return aa < bb || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(begin(arr), end(arr), [](auto &a, auto &b) {
            int aa = __builtin_popcount(a);
            int bb = __builtin_popcount(b);
            return aa < bb || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

And:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(begin(arr), end(arr), [](auto &a, auto &b) {
            int aa = std::bitset<32>(a).count();
            int bb = std::bitset<32>(b).count();
            return aa < bb || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(begin(arr), end(arr), [](auto &a, auto &b) {
            int aa = std::bitset<32>(a).count();
            int bb = std::bitset<32>(b).count();
            return aa < bb || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

Please note that the std::sort() algorithm takes O(NLogN) time complexity.

Another similar implementation with the help of Lambda: Please note that we are removing the Least Significant Bit until the number reaches zero – which to count the number of set ones.

1

#define LSB(x) ((x) & (-x))

#define LSB(x) ((x) & (-x))

And we then can do this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        function<int(int)> bitCount = [](int a) {
            int cnt = 0;
            while (a) {
                a -= LSB(a);
                cnt ++;
            }
            return cnt;
        };
        sort(begin(arr), end(arr), [&](auto &a, auto &b) {
            int aa = bitCount(a);
            int bb = bitCount(b);
            return (aa < bb) || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        function<int(int)> bitCount = [](int a) {
            int cnt = 0;
            while (a) {
                a -= LSB(a);
                cnt ++;
            }
            return cnt;
        };
        sort(begin(arr), end(arr), [&](auto &a, auto &b) {
            int aa = bitCount(a);
            int bb = bitCount(b);
            return (aa < bb) || ((aa == bb) && (a < b));
        });
        return arr;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —