CareerCup

It is just 11 bits. It makes 2048 numbers. You can build an array of 2048 elements and count how many time every number appeared.

For this problem, we cannot do better than linear time.

Counting sort is sufficient enough!

int[] input = {10,20,60,58,45,10,200,2001,485,95,85,545,458,487,545,120,121,2020,1,2,10,20};
        int[] arr = new int[2024];
        for(int i=0;i<arr.Length;i++){
            arr[i] =0;            
        }
        
        for(int i =0;i<input.Length;i++){
            arr[input[i]] +=1;  
        }
        
        for(int i=0;i<arr.Length;i++){
            if(arr[i]!=0){
                Console.WriteLine(i+ "---> " + arr[i]);
            }
        }

As its says 11 bits - we should probably use Radix Sort

It is just 11 bits. It makes 2048 numbers. You can build an array of 2048 elements and count how many times every number appeared.

Using constant memory and in linear time (θ(n)) in Java.

public static void main(String[] args) {
        int[] input = {4, 1, 4, 5, 512, 6, 1, 3, 754, 5, 523, 67, 51, 8, 9, 345, 599, 2032, 2011, 300, 12};
        int[] counts = new int[2048];
        for (int i = 0; i < 2048; i++) {
            counts[i] = 0;
        }

        for (int number : input) {
            counts[number]++;
        }

        int ptr = 0;
        for (int count = 0; count < 2048; count++) {
            for (int i = 0; i < counts[count]; i++) {
                input[ptr] = count;
                ptr++;
            }
        }
        System.out.println(Arrays.toString(input));
    }

public void sort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}

	int[] res = new int[1 << 11];
	for (int i : arr) {
		++res[i];
	}
	for (int i = 0, pos = 0; i < res.length; pos += res[i++]) {
		Arrays.fill(arr, pos, pos + res[i], i);
	}
}