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 Setbitcount1
Setbitcount1 obj = new Setbitcount1();
//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-3
arr = 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 19
The sorted arrange as per the set bits are:
2 4 3 5 6 7 11 19
The input array:
2 6 18 24 30 36 42
The sorted arrange as per the set bits are:
2 6 18 24 36 42 30
The input array:
48 42 36 30 24 18 12 6
The 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 integer
public static int cntSetBits(int num)
{
int cnt = 0;
while (num != 0)
{
// applying the bitwise operator
cnt = 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 method
public static void main(String argvs[])
{
// creating an object of the class SetBitCntSort1
Setbitcount2 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 3
arr = 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 19
The sorted arrange as per the set bits are:
2 4 3 5 6 7 11 19
The input array:
2 6 18 24 30 36 42
The sorted arrange as per the set bits are:
2 6 18 24 36 42 30
The input array:
48 42 36 30 24 18 12 6
The 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.