Approach
We can solve the problem using a greedy approach. You can easily observe that we can deal with the problem separately for each unique element in the array.
Let's say that element ‘X’ is present in the array. Let the frequency of this element be ‘Y’. Now, if Y > X, we are bound to delete excess occurrences of this element. Otherwise, if Y <= X, we are left with two choices:
 Either insert X  Y to the array.
 Delete Y occurrences of the elements.
It is not hard to see that we should take the minimum of these two values to minimise the overall number of operations. We can store the frequency of unique elements in the array using a hash map.
Algorithm
 Take the input array size ‘N’ and the array ‘ARR’ elements.
 Create an unordered map (or HashMap in Java) to store the frequency of each unique array element.
 Create a variable ‘MIN_OPERATIONS’ to store the answer.

Traverse the unordered map and let the current element be ‘ELEM’ and ‘FREQ’ be its frequency.
 If ELEM < FREQ, MIN_OPERATIONS += FREQ  ELEM.
 Otherwise, MIN_OPERATIONS += min(ELEM  FREQ, FREQ). These conditions are explained in the approach.
 Return MIN_OPERATIONS.
Program
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int getMinOperations(int N, vector<int>& arr){
// Store the frequency of all elements.
unordered_map<int,int> frequency;
for(int i = 0; i < N; i++){
frequency[arr[i]]++;
}
// Get the minimum number of operations.
int minOperations = 0;
for(auto uniqueElem : frequency){
// Get the current element and its frequency.
int elem = uniqueElem.first;
int freq = uniqueElem.second;
// First case described in the approach.
if(freq > elem){
minOperations += (freq  elem);
}
// Second case described in the approach.
else{
minOperations += min(elem  freq, freq);
}
}
// Return the output.
return minOperations;
}
int main(){
// Enter the size of the array.
int N;
cout << "Size of the array: ";
cin >> N;
// Enter the elements.
vector<int> arr(N);
cout << "Enter the elements: ";
for(int i = 0; i < N; i++){
cin >> arr[i];
}
// Get the output.
int ans = getMinOperations(N, arr);
cout << ans << endl;
}
Input
Size of the array: 5
Enter the elements: 2 1 3 1 2
Output
2
Time Complexity
The time complexity of the above approach is O(N), where ‘N’ is the size of the array.
It is because, for each element, we are taking a constant amount of time to determine its frequency in the final array.
Space Complexity
The space complexity of the above approach is O(N), where ‘N’ is the size of the array as the size of the unordered_map can grow to N.
Key Takeaways
In this blog, we discussed a simple yet tricky question involving greedy algorithms. Greedy algorithms are one of the wellknown topics asked in programming contests and technical interviews. Greedy algorithms are more or less used to test the common sense of the interviewee. Greedy algorithms should be used in problems where we find monotonicity in the result based on specific input factors.
Check out this problem  Search In Rotated Sorted Array