AVGSURV - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
You can choose and delete an element if it’s smaller than the average of the whole array.

Find the minimum number of elements that can be left in the array after deletions.

EXPLANATION:

Let’s look at the smallest element of the array, \min(A).

There are two possibilities:

  1. All the elements of the array are equal to \min(A).
    In this case, the average of the array is also \min(A), and so no more elements can be deleted.
  2. Not all elements of the array are equal to \min(A).
    In this case, the average of the array will be strictly larger than \min(A).
    So, it’s definitely possible to delete \min(A) from the array.

Thus, as long as not all elements are equal to the minimum, we are able to delete the minimum element from A.
This is equivalent to saying: as long as not all the elements of A are equal, we are able to delete an element from A.

Now, let M = \max(A).
Observe that no matter what, M can never be strictly less than the average of the array.
So, we cannot ever delete an occurrence of M from the array.

However, we’re able to delete all other elements by simply deleting the minimum element each time till we end up with just all copies of M.
Thus, in the end, the remaining elements are simply all the copies of M in the initial array.

Thus, the answer is the number of elements equal to \max(A) in the array A.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    mx = max(a)
    print(a.count(mx))