17. Sort array by set bit count

17. Sort array by set bit count

Problem link :- click here

package program;

import java.util.Arrays;
import java.util.Comparator;

public class Searching__17
{

	/*
	 	Given an array of integers, sort the array (in decreasing order)
	 	according to count of set bits in binary representation of array elements.
	 			arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32}
	 			output : {15, 7, 5, 3, 9, 6, 2, 4, 32}
	 			
	 	we will use comparator to solve this problem
	 */
	
	static Integer[] sortByBitCount(Integer arr[], int n)
	{
		Arrays.sort(arr, new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b)
			{
				int x = Integer.bitCount(a);
				int y = Integer.bitCount(b);
				if(x == y)
					return 0;
				else if(x < y)
					return 1;
				else
					return -1;
			}
		});
		
		return arr;
	}
	
	
	public static void main(String[] args)
	{
		Integer arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32};
		System.out.println("Array before sorting : ");
		printIntegerArray(arr);
		arr = sortByBitCount(arr, arr.length);
		System.out.println("\nArray after sorting : ");
		printIntegerArray(arr);
	}

	static void printIntegerArray(Integer arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n log(n))
Space complexity :- O(1)