PROBLEM LINK:
Author: mesksr
Editorialist: mesksr
DIFFICULTY:
EASY
PREREQUISITES:
Math, Fast Modular Exponentiation
PROBLEM:
Given a list of the integers, we have to tell the number of ways of selecting integers such that thier arithmetic mean is maximum.
EXPLANATION:
We can get maximum arithmetic mean, only when one or more occurances of maximum element of list is selected. (like in second example we selected {90}, {90} and {90,90})
So, we need to count the number of times (say c) the maximum element of list occurs.
Now, the answer will be 2^c - 1.
2^c means : for each of c elements, we are either selecting it or not. (for second example c = 2, 2^c denotes {}, {90}, {90}, {90,90})
-1 : for removing the case when we did not select any of the c elements. (removing this -> {})
To calculate 2^c, we can get TLE if c is very large. So, we will use Fast Modulo Multiplication. Read more about it here
AUTHOR’S SOLUTION:
Author’s solution can be found here.