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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Add two numbers in Scala - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Goal Parser Interpretation LeetCode Solution - The Coding Shala

Maximum Population Year LeetCode Solution - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala