 # 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.

### Java:

``````class Solution {
public int[] sortByBits(int[] arr) {
List<Integer> ordered = new ArrayList<>();
int n = arr.length;
for (int i = 0; i < n; 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)

Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.