AVGFLEXP - Editorial

editorial
, ,
1

Problem Link - Average Flex in Binary Search

Problem Statement:

There are N students in a class, where the i-th student has a score of A_i. The i-th student will boast if and only if the number of students scoring less than or equal to A_i is greater than the number of students scoring greater than A_i. Find the number of students who will boast.

Approach:

  • To efficiently count the number of scores less than or equal to a particular score, we sort the array of scores.
  • Using upper_bound: For each student’s score $A[i]4, we find the position where A[i] would fit in the sorted array (using upper_bound). The distance from the beginning of the array to this iterator gives us the count of elements that are less than or equal to A[i].
  • Specifically, upper_bound(v, v+n, v[i]) - v computes the number of students who have a score less than or equal to A[i].
  • Calculate the number of students scoring greater than A[i] as n−d (where d is the count of students scoring less than or equal to A[i]).

Complexity:

  • Time Complexity: The main operations include sorting the array, which is O(NlogN), and iterating through the array to calculate boasting students, which is O(N). The overall complexity is O(NlogN).
  • Space Complexity: O(1).