Leetcode 1356: Sort Integers by The Number of 1 Bits

In this Leetcode problem, we are asked to sort the integer, but not in the natural ordering, instead integers are sorted by the number of 1s in their binary representation.

Here is the problem statement:

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.

Problem statement and examples

Solution

One thing to notice is that since there are duplicates (Example 3), therefore using a TreeSet that would be sorted is not possible. We could use a TreeMap with the values as keys and the number of occurrences as values. But I went another way.

Instead I built a list, sorted it using a comparator, and transformed it to an array.

Another and probably better solution would be to sort array directly with Arrays.sort(), but I usually prefer to work with Java collection (personal preference).

We count the bits using bit mask and bit shifting strategy:

public int bitNumber(int x) {
    int res = 0;
    while (x != 0) {
        int i = x & 1;
        res += i;
        x = x >> 1…