Sorting would be enough.
Given scores of N teams, and an integer K, the number of teams from the top to qualify, Find out number of teams qualify if in case of tie at Kth position, All teams tying with Kth team will also qualify.
SUPER QUICK EXPLANATION
- Sort the scores, and count number of teams having score greater than or equal to Kth team. (Shortest explanation ever from my side :P)
As the problem statement itself mentions, Teams will be sorted in descending order by their score and Top K teams will be selected.
First of all, Assume that all scores are distinct. Now, we are sure that there won’t be any tie for Kth rank. Exactly K teams will qualify.
Now, when two or more teams can score same, either all of them will qualify, or none of them. So, we just need to find the score X such that all teams with score s* /geq X will qualify, while teams with s* < X will not.
We can see that X is actually the score of Kth team, if all teams are sorted by their score.
So, we can just sort the scores, find X and iterate over all elements, increasing answer by one whenever we see a team with s* \geq X.
Problems for Practice can be found here.
Time complexity is O(N*logN) due to sorting. Iterating over the elements takes O(N) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.