Karl Max - 7 months ago 38

C Question

I want to find the fastest way to find the number of elements which are smaller/greater than each element in an array.

**For example** : Array is [5, 6, 8, 2, 4]. Considering first element, no of elements smaller than it is 2.

The best I could make myself was that each element be compared with the rest of the array elements but it takes a long time for large arrays with number of entries approx 10^5.

My code:

`for(i=0;i<n;i++)`

{

count=0;

for(j=0;j<n;j++)

{

if( i!=j && (ar[i]>ar[j]) )

{

count++;

}

}

printf("%lld ",count);

}

And the

Answer

A simple approach will be:

- Sort the array first, possibly using
`qsort()`

- Perform a binary search on the sorted array.
- Calculate the remaining elements
*from*the desired elements, based on the size of the array.