Sort An Array according to number of set bits

Sort An Array according to number of set 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: [0,1,2,3,4,5,6,7,8]

Output: [0,1,2,4,8,3,5,6,7]

Example 2:

Input: [1,5,7,13,17,21,23,25]

Output: [1,5,17,7,13,21,25,23]

Constraints:

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

Solution:

This is not a usual solution of just sorting the numbers in ascending, instead we need to see number of 1 bit in the number then sort them according to the number of 1 bit. We first built a list. Sorting can be done using comparator and counting is done using bit mask and by bit shifting strategy. We at last transform our resulting values into an array.

Implementaion:

Java:

class Solution {
    public int[] sortByBits(int[] arr) {
        List<Integer> ordered = new ArrayList<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            ordered.add(arr[i]);
        }
        Collections.sort(ordered, (x, y) -> {
            int xbit = bitNumber(x);
            int ybit = bitNumber(y);
            if (xbit < ybit) {
                return -1;
            }
            if (xbit > ybit) {
                return 1;
            }
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }
            return 0;
        });
        int[] res = new int[n];
        int i = 0;
        for (int x : ordered) {
            res[i] = x;
            i++;
        }
        return res;
    }

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

Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(n)