One day Jay, on getting his first salary, decides to distribute apples among the poverty-stricken persons. He gave each person 1kg of apples. People are coming in a queue and he makes sure that he gives every person 1 kg of apples only once. Every person is identified by a specific integer.
Given the length of the queue N followed by an array of N integers, denoting the persons in that queue, find the minimum kilograms of apples Jay will have to distribute.
Example 1:
​Input : arr[ ] = {1, 1, 1, 1, 1}
Output : 1
Explanation:
For test case 1, the same person (identified
by the integer '1' comes again and again in
the queue, but Jay will not give him apples
again and again. He gave him apples only
once so minimum kg's of apples here
required-1kg).
​Example 2:
Input : arr[ ] = {1, 2, 3, 1, 2}
Output : 3
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function minimum_apple() that takes an array (arr), sizeOfArray (n) and return the minimum kilograms of apples Jay will have to distribute. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 105
1 ≤ Ai ≤ 105