# Sort An Array According to The Count of Set Bits in Java

Sorting an array according to the count of set bits involves arranging the elements of the array in ascending order based on the number of set bits (binary 1s) in their binary representations.

Example 1:

Input: array[] = {2, 3, 4, 5, 6, 7, 11, 19};

Output: 2 4 3 5 6 7 11 19

Explanation:

The integers in their binary representation are:

2 -> 10

3 -> 11

4 -> 100

5 -> 101

6 -> 110

7 -> 111

11 -> 1011

19 -> 10011

From the above example, if we sort the above numbers according to set bits, we get the following order

{2,4} -> Only 1 set bit

{3,5,6} -> 2 set bits

{7,11,19} -> 3 set bits

Hence, the output will be {2, 4, 3, 5, 6, 7, 11, 19}

Example 2:

Input: array[] = {2, 6, 18, 24, 30, 36, 42};

Output: 2 6 18 24 36 42 30

Explanation:

The integers in their binary representation are:

2 -> 10

6 -> 110

18 -> 10010

24 -> 11000

30 -> 11110

36 -> 100100

42 -> 101010

From the above example, if we sort the above numbers according to set bits, we get the following order

{2} -> Only 1 set bit

{6, 18, 24, 36} -> 2 set bits

{42} -> 3 set bits

{30} -> 4 set bits

Hence, the output will be {2, 6, 18, 24, 36, 42, 30}

Example 3:

Input: array[] = {48, 42, 36, 30, 24, 18, 12, 6};

Output: 48 36 24 18 12 6 42 30

Explanation:

The integers in their binary representation are:

48 -> 110000

42 -> 101010

36 -> 100100

30 -> 11110

24 -> 11000

18 -> 10010

12 -> 1100

6 -> 110

From the above example, if we sort the above numbers according to set bits, we get the following order

{48, 36, 24, 18, 12, 6} -> 2 set bits

{42} -> 3 set bits

{30} -> 4 set bits

Hence, the output will be {48, 36, 24, 18, 12, 6, 42, 30}

Let us try to understand the following program.

## Approach: Using Map

Step 1: Create a class that contains methods for counting set bits and sorting based on set bits count.

Step 2: Createa method that takes input as an integer and outputs the number of set bits. This method calculates and returns the count of set bits (1s) in an integer using bitwise operations.

Step 3: For Sorting based on set bits,create another method that takes input as an ArrayList of integers with a certain size. Use HashMap to group numbers based on their set bit count. After processing, clear the input ArrayList and populate it with the sorted numbers based on the set bit count.

Step 4: The input and sorted arrays are printed to the console.

File name: Setbitcount1.java

`import java.util.HashMap;  import java.util.Arrays;  import java.util.ArrayList;  public class Setbitcount1  {  //Method for counting the set bits numbers in an integer  public static int cntSetBits(int num)  {  int cnt = 0;  while (num != 0)  {  cnt = cnt + (num & 1);  num = num / 2;  }  return cnt;  }  public  void sortSetBitsCount(ArrayList<Integer> arr, int siz)  {   // creating an object of the class HashMap HashMap<Integer, ArrayList<Integer>> res = new HashMap<>();  for (int j = 0; j < siz; j++)  // store the set bits count in the variable ky   {  int ky = cntSetBits(arr.get(j));  ArrayList<Integer> val = new ArrayList<>();  if (res.containsKey(ky))  {  val.addAll(res.get(ky));  }  val.add(arr.get(j));  res.put(ky, val);  }  arr.clear();    for (int j = 0; j <= 32; j++)  {  if (res.containsKey(j))  {  arr.addAll(res.get(j));  }  }  for(int i = 0; i < siz; i++)  {  System.out.print(arr.get(i) + " ");  }  }  public static void main(String argvs[])  //main method{    // creating an object of the class Setbitcount1Setbitcount1 obj = new Setbitcount1();  //Input-1ArrayList<Integer> arr = new ArrayList<Integer> (  Arrays.asList(2,3,4,5,6,7,11,19));  int size = arr.size();System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);  System.out.println( "\n" );  //Input-2arr = new ArrayList<Integer> (  Arrays.asList(2,6,18,24,30,36,42));  size = arr.size();  System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);System.out.println( "\n" );  //Input-3arr = new ArrayList<Integer> (  Arrays.asList(48,42,36,30,24,18,12,6));  size = arr.size(); // computing its size  System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);  }  }`

Output:

`The input array:2 3 4 5 6 7 11 19The sorted arrange as per the set bits are:2 4 3 5 6 7 11 19The input array:2 6 18 24 30 36 42The sorted arrange as per the set bits are:2 6 18 24 36 42 30The input array:48 42 36 30 24 18 12 6The sorted arrange as per the set bits are:48 36 24 18 12 6 42 30`

Complexity analysis:

The time complexity of the given code is O(N * log N), where N is the size of the input array.

## Approach: Using Customized Comparator

Step 1: Create a class that implements the interface for integers. Inside the class, define a method for counting set bits in an integer using bitwise operations.

Step 2: Implement the method from the interface to compare integers based on the count of set bits.

Step 3: Inside the main class, define a method that takes an ArrayList of integers and its size as input. Use Collections.sort to sort the ArrayList based on set bit count.

Step 4: Call the method to sort and print the arrays based on the set bit count.

File name: Setbitcount2.java

`import java.util.Collections;  import java.util.Comparator;  import java.util.ArrayList;  import java.util.Arrays;  class sortComparator implements Comparator<Integer>  {    // Method for counting the set bits numbers in an integerpublic static int cntSetBits(int num)  {  int cnt = 0;  while (num != 0)  {  // applying the bitwise operatorcnt = cnt + (num & 1);  num = num / 2;  }  return cnt;  }   // Comparator for the sort method @Override  public int compare(Integer n1, Integer n2)  {  return cntSetBits(n1) - cntSetBits(n2);  }  }  public class Setbitcount2{  public  void sortSetBitsCount(ArrayList<Integer> arr, int siz)  {  Collections.sort(arr, new sortComparator());  for(int i = 0; i < siz; i++)  {  System.out.print(arr.get(i) + " ");  }  }     // Main methodpublic static void main(String argvs[])  {  // creating an object of the class SetBitCntSort1Setbitcount2 obj = new Setbitcount2();  // input 1  ArrayList<Integer> arr = new ArrayList<Integer> (  Arrays.asList(2,3,4,5,6,7,11,19) );  int size = arr.size();System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);  System.out.println( "\n" );  // input 2  arr = new ArrayList<Integer> (  Arrays.asList(2,6,18,24,30,36,42));  size = arr.size();System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);System.out.println( "\n" );  // input 3arr = new ArrayList<Integer> (  Arrays.asList(48,42,36,30,24,18,12,6));  size = arr.size();System.out.println("The input array: ");  for(int i = 0; i < size; i++)  {  System.out.print(arr.get(i) + " ");  }  System.out.println( );  System.out.println("The sorted arrange as per the set bits are: ");  obj.sortSetBitsCount(arr, size);  }  }`

Output:

` The input array:2 3 4 5 6 7 11 19The sorted arrange as per the set bits are:2 4 3 5 6 7 11 19The input array:2 6 18 24 30 36 42The sorted arrange as per the set bits are:2 6 18 24 36 42 30The input array:48 42 36 30 24 18 12 6The sorted arrange as per the set bits are:48 36 24 18 12 6 42 30`

Complexity Analysis: The time complexity of the provided code is O(N * log N), where N is the size of the input ArrayList.