PROBLEM LINK:
Author: Suraj Prakash
Tester: Aditya Kumar
Editorialist: Suraj Prakash
DIFFICULTY:
Easy
PREREQUISITES:
Ad-hoc, Binary Search
PROBLEM
Compute the count of elements (floating point decimals) greater than K, if the list of non repeating elements was sorted.
EXPLANATION
To find the number of elements greater than K, what we can do is to simply iterate through the array and count the number of elements greater than K, this is an approach which will run in time for smaller constraints. This will lead to a complexity of \mathcal{O}(N * Q)
For better efficiency this can be done using binary search in \mathcal{O}(\log (N) * Q), since we need to count the number of elements greater than K.
int find(vector<double> &v, int l, int h, double f){
int low = l, high = h, mid;
while (low < = high){
mid = (low + high) >> 1;
if (v[mid] == f)
return (h - mid);
else if (v[mid] > f)
high = mid - 1;
else
low = mid + 1;
}
return h - low + 1;
}
STL offers inbuilt binary search which can be used to solve this problem using a line of code.
N - (upper_bound(arr, arr + N, K) - arr)
OPTIMAL COMPLEXITY:
\mathcal{O}(Q*\log(N))
AUTHOR’S SOLUTION:
Author’s solution can be found here.
Tester’s solution will be uploaded soon.