Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is HashMap data structure?
4.2.
Is sort in C++ STL?
4.3.
What is the time complexity of sort function in C++ STL?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum Number of Distinct Elements after Removing M items

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

In this blog, we will discuss a problem in which we have to print the Minimum number of distinct elements after removing m items. We will be using the Hashmap data structure for solving the question.

A HashMap is a data structure that can map certain keys to specific values. The keys and values could be anything. Each data value has a unique index value in a hash table, which stores data in an array format. If we know the index of the needed data, data access becomes very fast. As a result, it develops into a data structure in which insertion and search operations, regardless of the size of the data, are very fast.

Problem Statement

Ninja has given you an array of items, a number m. The i-th index element shows the item's id. Your task is removing m elements until just minimum distinct elements are left. Print the total count of the minimum number of distinct elements left after removing M items.

Sample Examples

Example 1

Input

Enter the value of m : 3

Output

1

 

Explanation: We have to remove 3 elements from the array so we start removing the elements with the least occurrence, so we remove 1 and both 2. Hence we are left with minimum distinct element 3 i.e., 1.

 

Example 2

Input

Enter the value of m : 2

Output

2

 

Explanation: We have to remove 2 elements from the array so we start removing the elements with the least occurrence, so we remove 1 and 3. Hence we are left with minimum distinct elements 2 and 4 i.e., 2.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The idea is to store each element's occurrence in a hash and then count the occurrence of each frequency in a hash again. Then we will sort the frequency of occurrences of each element in increasing order and will start removing the element whose frequency is less or equal to m.

Algorithm

  1. Create a hashmap to store the occurrence of elements.
  2. Count the occurrence of all elements and store them in the hash.
  3. Sort the hash in increasing order.
  4. Remove the elements whose frequency is less than m from the hashmap.
  5. Print the number of elements present in the hash.

Implementation in C++

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

#define pb push_back

int hash_fun(int arr[], int n, int m)
{
    int temp = 0;
    // hashmap for storing the occurence
    unordered_map<int, int> mp;
    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++)
        mp[arr[i]]++;

    // use vector to store the pair key with its occurrence
    for (auto i = mp.begin(); i != mp.end(); i++)
        v.pb(make_pair(i->second, i->first));

    sort(v.begin(), v.end()); // sorting the vector

    int vec_size = v.size();

    for (int i = 0; i < vec_size; i++)
    {
        // Remove the value if it is less than or equal to m
        // else return the remaining size
        if (v[i].first <= m)
        {
            m = m - v[i].first;
            temp++;
        }
        else
            return vec_size - temp;
    }
    return vec_size - temp;
}

int main()
{
    int m;
    int arr[] = {3, 1, 2, 2, 3, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Enter the value of m : ";
    cin >> m;
    cout << endl;

    cout << hash_fun(arr, size, m);
    return 0;
}

 

Input

Enter the value of m : 3

 

Output

1

Time Complexity

The time complexity of the above approach is O(NlogN) because we have used sorting, which marks the upper bound for time complexity.

Space Complexity

The space complexity of the approach is O(N), as we are storing the elements as a key in the hashmap.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is HashMap data structure?

A HashMap is a data structure that can map certain keys to a specific value. The values and keys could be anything.
 

Is sort in C++ STL?

A C++ Standard Template Library(STL) includes a built-in function called sort(). The elements in the range can be sorted using this function in either ascending or descending order.
 

What is the time complexity of sort function in C++ STL?

The worst-case time complexity of sort() is in O(n log n), where n is the number of sorted elements.
 

Also Read - Strong number in c

Conclusion

In this article, we have extensively discussed the problem of printing the minimum number of distinct elements after removing m items. We solved the problem using the hashmap data structure and discussed its time as well as space complexity.

We hope that this blog has helped you enhance your knowledge about the count of minimum distinct elements and if you like to learn more, check out our articles Implementation of HashMapSorting Based ProblemsSTL in C++, and many more on our Website.

Recommended Problems - 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Numbers with prime frequencies greater than or equal to k
Next article
Check If Two Given Sets Are Disjoint
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass