# STUDY - Editorial

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

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;
}
``````
1 Like