Pre-requisites: Implementation, Maths
We are given array A, that consists of N integers. We need to count the number of subsets of A, whose arithmetical mean is maximal. Arithmetical mean of an empty subset is undefined.
Let’s define MAX-VALUE as the maximal number of A.
The answer is two to the power NUM-MAX-VALUE minus one, where NUM-MAX-VALUE is the number of times MAX-VALUE appears in A.
Let’s have a look why the previous statement is correct.
Arithmetic mean of a set of numbers is smaller than or equal to the maximal number. Then, any subset of A, that contains only numbers that are equal to MAX-VALUE, is suitable and gives the maximal arithmetical mean, which equals to MAX-VALUE.
At the same time, if there is one number chosen, that is smaller than MAX-VALUE, then the arithmetical mean would be smaller than MAX-VALUE.
That’s why the answer is 2^NUM-MAX-VALUE - 1.
Why we should subtract 1? Because one of the subsets, that we have counted, is empty. We mustn’t consider it as a subset, that gives the the maximal arithmetical mean.
Setter’s Solution: link
Tester’s Solution: link