### PROBLEM LINK:

**Author:** Abhra Dasgupta

**Tester:** Kevin Atienza

**Editorialist:** Ajay K. Verma

**Russian Translator:** Sergey Kulik

**Mandarian Translator:** Gedi Zheng

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Basic maths

### PROBLEM:

Given N numbers, find the smallest value M such that any collection of M of the given numbers is guaranteed to have at least two entries of each number.

### EXPLANATION:

If there is at least one number which is present only once in the original set of N numbers, then we can never find a collection where each number occurs at least twice. Hence, the answer in this case would be -1.

Now, we know that each number occurs at least two times in the original set of numbers. Let us say that number x has the least number of occurrences (f). Now, if we take any collection of (N - f + 2) numbers, it will have at least two entries of each number. This is because only (f - 2) are missing in this collection, and since each number has at least f entries, it will have at least two entries in the picked collection.

On the other hand, we can take a collection of (N - f + 1) numbers, consisting of all (N - f) numbers other than x, and a single entry of x, which contains only a single entry of x. Hence, the answer to our problem should be (N - f + 2).

In the problem, we are not given the whole list of numbers; instead we are given the frequency of each number. Hence, we need to compute the total number of all ingredients, and the smallest frequency, as shown in the snippet below.

// A[] is the input array, which consists of the frequencies of elements. int sum = 0; int minFreq = INF; for (int i = 0; i < A.size(); ++i) { sum += A[i]; minFreq = min (minFreq, A[i]); } if (minFreq == 1) return -1; return (sum - minFreq + 2);

#### Time Complexity:

O (N)