### Sort an Array According to Count of 1(set) bits - The Coding Shala

Home >> Interview Questions >> Sort an array based on set bits

In this post, we will learn how to sort an integer array in ascending order by the number of 1's in their binary representations.

## Sort an Array According to Count of Set(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.

Example 1:
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explanation: [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]
Explanation: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

## Sort an Array According to Count of Set bits Java Solution

Approach 1

We can use a custom comparator to sort the array.

Java Program:

```class Solution {
public int[] sortByBits(int[] arr) {
Integer[] tmp = new Integer[arr.length];
for(int i=0;i<arr.length;i++) tmp[i]=(Integer)arr[i];
Arrays.sort(tmp, new Comparator<Integer>()
{
@Override
public int compare(Integer a, Integer b){
int c1 = Integer.bitCount(a);
int c2 = Integer.bitCount(b);
if(c1<c2) return -1;
else if(c1 == c2) return a - b;
else return 1;
}
});
for(int i=tmp.length-1;i>=0;i--) arr[i]=(int)tmp[i];
return arr;
}
}
```

Other Posts You May Like