Question

Let A be an array of N distinct positive numbers such that at most sqrt(N) of them is larger than N.

Ex: if N=100, there are at most 10 elements in A that are greater than 100.

1. Split A into A1 and A2 such that A1 contains the elements greater than N and A2 contains the remaining elements. Do this in O(N)

2. Sort A1 in O(N)

3. Sort A2 in O(N)

4. Sort A in O(N)

I don't need actual code, more so it explained clearly. I was under the impression 3 and 4 would be impossible. Thanks!

Answer 1

(1) Simply iterate the array A and if current element is smaller than or equal to n insert it into A2 else insert it into A1.this takes o(n) time.

(2)to sort A2 simply use bubble sort because size of A2 is atmost sqrt(n) hence time complexity for bubble sort will b o(sqrt(n)^2)=o(n)

(3)To sort A2 because hash map of array B of size 'n' and iterate the A2 array and increase count of current element index in B i.e B[A[i]]++ now once the whole of array A2 is processed iterate array B and replace elements of A2 by current index of array B if its counter is >0 and do this for every index of B for value of counter at that index then proceed to next index once as many as current index is inserted to A2 as value of counter at that index. this is o(n)

(4) to sort A now use technique similar to we use in merge operation for two arrays A1 and A2 as in merge sort of two array.

i=0;

j=0;

k=0;

while(i<A1.size()&&j<A2.size())

{

if(A1[i]<A2[j])

A[k++]=A1[i++];

else

A[k++]=A2[j++];

}

//please upvote if this was helpful.