### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Utkarsh Lath

**Editorialist:** Balajiganapathi Senthilnathan

**Russian Translator:** Sergey Kulik

**Mandarian Translator:** Gedi Zheng

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

None

### PROBLEM:

There are **n** people and the i_{th} of them wants a party on the d_i^{th} day. Devu can give at most one party in a day. What is the maximum number of people who can take parties from Devu?

### SHORT EXPLANATION

- Answer will be the number of distinct days.

### EXPLANATION:

Since Devu can give only one party each day. So if more than one people want a party on a day, then he can give party to only one of them. Also, if nobody wants a party on a particular day, then Devu won’t give a party on that day. So it means that number of parties given by Devu will be number of days on which people are asking parties. In other words, it is equal to number of distinct elements in the array d.

**Finding number of distinct elements in an array**

There are a lot of ways of finding number of distinct elements in an array. The most basic idea is to maintain number of occurrences of of each element in the array and then our answer will be number of elements having non zero number of occurrences.

For maintaining count of elements in the array, we can make an look up array whose i-th element denotes number of occurrences of element i.

**Pseudo Code**

int cnt[101]; // (since 1 <= d_i <= 100) // fill the cnt array. for (int i = 1; i <= n; i++) { cnt[d[i]]++; } // Now check number of elements having non zero count. int ans = 0; for (int i = 1; i <= 100; i++) { if (cnt[i] > 0) { ans++; } }

Time complexity of the above algorithm is \mathcal{O}(100 + n) which is \mathcal{O}(n).

**Another way of finding number of distinct elements in the array**

First let us sort the array d. Now, we can notice that all equal elements will appear continuously in the array. So, we will go from left to right in the sorted order and will count only first occurrence of each element.

Time complexity of this method will be \mathcal{O} (n log n)

**Yet another way of finding number of distinct elements in the array**

You can use STL (standard template library) data structure set which maintains only unique elements in the sorted order. So all we need to do is add all the numbers in the set and finally find the size of the set.

**Pseudo Code**

set st; // insert all the array elements into the set for (int i = 1; i <= n; i++) { st.insert(d[i]); } // Size of set can be found using .size() function int ans = st.size();

Time complexity of each insertion in set is \mathcal{O}(log n). As we are inserting n elements in the array, so overall time will be \mathcal{O}(n log n)