STUDY - Editorial

editorial
1

PROBLEM LINK:

Contest

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

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