PROBLEM LINK:
Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Linear Search
PROBLEM:
Given a sorted array S of integers S0 to SN, the task is to determine how many Si, where 0$<i<=$N are greater than S0.
EXPLANATION:
A simple linear search to find the number of elements larger than S0 is sufficient to pass the checker. A binary search to find the smallest element larger than S0 can be performed. Because the array is sorted we know every element to the right of it is also greater than S0, thus we can deduce the answer. This can be done in O(log n) time instead of O(n) if done by linear search.
However, since taking input itself takes linear time, binary search offers no advantage here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.