Here is the simplified problem statement.
Given a list of scores of contestants in a competition, arranged in decreasing order. We have to calculate the number of people qualified for the next round.
This is determined as follows, consider the score at a given index, Whoever scored more than this score, qualifies for the next round as long as they have a score of greater than zero.
For example, let us consider the scores {10, 9, 8, 7, 7, 7, 5, 5} and the index (starts from 1) to take as bench mark is 5. we have a total of 6 candidates who qualify for next round.
If the scores are {0,0,0,0} and the index is 2, no one qualifies for the next round because none of them have a score greater than zero.
Let us look at the way of solving this problem. We have to handle two cases here.
Case 1: score[index] > 0
In this case, we have to find the right most occurrence of the cutoff, which will give the required answer
Case 2: score[index[ <= 0
In this case, we have to find the left most occurrence of zero, and count the remaining elements from the beginning.
Here is the C++ implementation of the above. Since finding the left most and right most elements in a sorted array can be found using binary search, the time complexity of this solution is O(log n).
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| int leftMost( vector<int>& nums, int s ) | |
| { | |
| int l = 0, h = nums.size()-1; | |
| while ( l <= h ) | |
| { | |
| int mid = l + (h-l)/2; | |
| if( nums[mid] == s ) | |
| { | |
| if( mid > 0 && nums[mid] == nums[mid-1] ) | |
| { | |
| h = mid-1; | |
| } | |
| else | |
| return mid; | |
| } | |
| else if( nums[mid] > s ) | |
| { | |
| h = mid-1; | |
| } | |
| else | |
| { | |
| l = mid+1; | |
| } | |
| } | |
| return -1; | |
| } | |
| int rightMost( vector<int>& nums, int s) | |
| { | |
| int l = 0, h = nums.size()-1; | |
| while ( l <= h ) | |
| { | |
| int mid = l + (h-l)/2; | |
| if( nums[mid] == s ) | |
| { | |
| if( mid < nums.size()-1 && nums[mid] == nums[mid+1] ) | |
| { | |
| l = mid+1; | |
| } | |
| else | |
| return mid; | |
| } | |
| else if( nums[mid] > s ) | |
| { | |
| h = mid-1; | |
| } | |
| else | |
| { | |
| l = mid+1; | |
| } | |
| } | |
| return -1; | |
| } | |
| int main() { | |
| int n,k; | |
| cin >> n >> k; | |
| vector<int> scores(n); | |
| int i; | |
| for( i = 0; i < n; i++ ) | |
| { | |
| cin >> scores[i]; | |
| } | |
| int cutoff = scores[k-1]; | |
| if( cutoff < 0 ) | |
| cutoff = 0; | |
| if( cutoff > 0 ) | |
| { | |
| int ind = rightMost(scores,cutoff); | |
| cout << ind+1 << endl; | |
| } | |
| else | |
| { | |
| vector<int>::iterator loIt; | |
| int ind = leftMost(scores,cutoff); | |
| if( ind <= 0 ) | |
| { | |
| cout << "0" << endl; | |
| } | |
| else | |
| { | |
| cout << ind << endl; | |
| } | |
| } | |
| return 0; | |
| } |
by