# PROBLEM LINK:

* Author:* Sumukh Bhardwaj

*Rahul Sharma*

**Tester:***Sumukh Bhardwaj*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Basic Programming

# PROBLEM:

Given an array of integers of size, N find the minimum of the number of distinct values in the array and N/2.

# QUICK EXPLANATION:

Count the frequency of all the elements and count the numbers having the frequency as 1, then find the minimum of N/2 and this count.

# EXPLANATION:

- Use a HashSet or Unordered_map to keep the frequency of each element in the array.
- Count the numbers having a frequency as 1.
- Return the minimum of N/2 and the above count.

# COMPLEXITIES

Here n is the size of array.

**TIme Complexity:** O(n).

This is because we must insert every number into the hash map and insertion into a hash map is a constant time operation.

**Space Complexity:** O(n).

We will need to store all of the numbers.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> &A) {
int i,cnt=0,n = A.size();
unordered_map<long long,long long>mark;
for(i=0;i<n;i++)
{
mark[A[i]]++;
if(mark[A[i]]==1)
cnt++;
}
return min(n/2,cnt);
}
int main() {
ios_base::sync_with_stdio(false);
int t,n,i;
cin>>t;
while(t--)
{
cin>>n;
vector<int> v(n);
for(i=0;i<n;i++)
cin>>v[i];
cout<<solve(v)<<endl;
}
return 0;
}
```