**Problem Link:** contest, practice

**Difficulty:** Cakewalk

**Pre-requisites:** Implementation, Maths

**Problem:**

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.

**Explanation:**

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