Given problem statment
Kiran Kumar is the Assistant Professor of Computer science department so he Just ask interact with the students and helps the students to solve the complex problems in an easier way so, the problem given by the sir is Sort an array according to count of set bits?
Example input and output
Input: arr[] = {1, 2, 3, 4, 5, 6}; Output: 3 5 6 1 2 4 Explanation: 3 - 0011 5 - 0101 6 - 0110 1 - 0001 2 - 0010 4 - 0100 hence the non-increasing sorted order is {3, 5, 6}, {1, 2, 4}
Java program to sort an array according to count of set bits
class sortArrayAccordingToCountOfSetBits {
static int countBits(int a) {
int count = 0;
while (a > 0) {
if ((a & 1) > 0)
count += 1;
a = a >> 1;
}
return count;
}
static void sortByCountOfSetBit(int arr[], int n) {
int setBitCount[] = new int[n];
for (int i = 0; i < n; i++)
setBitCount[i] = countBits(arr[i]);
for (int i = 1; i < n; i++) {
int bitCountKey = setBitCount[i];
int arrkey = arr[i];
int j = i - 1;
while (j >= 0 && setBitCount[j] < bitCountKey) {
setBitCount[j + 1] = setBitCount[j];
arr[j + 1] = arr[j];
j = j - 1;
}
setBitCount[j + 1] = bitCountKey;
arr[j + 1] = arrkey;
}
}
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = arr.length;
sortByCountOfSetBit(arr, n);
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}