Find minimum number of distinct elements after removing M items

Here, we are going to find the minimum number of distinct elements after removing M number of items from array.

Given: An array arr[] of items, an i‘th index element denotes the item id’s and given a number m.

Problem: Remove m elements such that there should be minimum distinct id’s left and then print the number of distinct id’s.

Example:

Input : arr[] = { 2, 2, 1, 3, 3, 3} 
            m = 3
Output : 1
Remove 1 and both 2's.So, only 3 will be 
left that's why distinct id is 1.
Input : arr[] = { 2, 4, 1, 5, 3, 5, 1, 3} 
            m = 2
Output : 3
Remove 2 and 4 completely. So, remaining ids 
are 1, 3 and 5 i.e. 3

Solution:

• Count the occurrence of elements and store in the hash.
• Sort the hash.
• Start removing elements from hash.
• Return the number of values left in the hash.

Program to Find minimum number of distinct elements after removing M items in C++:

// C++ program for above implementation 
#include <bits/stdc++.h> 
using namespace std; 
// Function to find distinct id's 
int distinctIds(int arr[], int n, int mi) 
{ 
    unordered_map<int, int> m; 
    vector<pair<int, int> > v; 
    int count = 0; 
    // Store the occurrence of ids 
    for (int i = 0; i < n; i++) 
        m[arr[i]]++; 
    // Store into the vector second as first and vice-versa 
    for (auto it = m.begin(); it != m.end(); it++) 
        v.push_back(make_pair(it->second, it->first)); 
    // Sort the vector 
    sort(v.begin(), v.end()); 
    int size = v.size(); 
    // Start removing elements from the beginning 
    for (int i = 0; i < size; i++) { 
        // Remove if current value is less than 
        // or equal to mi 
        if (v[i].first <= mi) { 
            mi -= v[i].first; 
            count++; 
        } 
        // Return the remaining size 
        else
            return size - count; 
    } 
    return size - count; 
} 
// Main
int main() 
{ 
    int arr[] = { 2, 3, 1, 2, 3, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int m = 3; 
    cout << distinctIds(arr, n, m); 
    return 0; 
} 

OUTPUT:

1

Time Complexity: O(n log n)

Please write comments if you find anything incorrect, or you want to share more information about finding the minimum number of distinct elements after removing M items.