Greedy: Reduce the array size to the half

Problem Statement:

You are given an array with repeated elements.

You can choose set of integers and remove all the occurrence of the integers from the array

You need to return the minimum size of the set so that half of the array is removed

Example

Input: arr = [6, 6, 6, 6, 6, 6, 6, 6, 6]
Output: 1
Explanation: The only possible set you can choose is {6}. This will make the new array empty.

Solution

You need to use greedy approach.

We get the frequency of each element in the array. We can get it by using unordered map.

Then we put that into a MaxHeap. So that the element that is occurring most time is at the top of the heap.

In C++ MaxHeap is implemented as priority_queue.

Then we start removing the element from the heap, until the size becomes less than the array size.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<unordered_map>

using namespace std;


int get_min_set_size(vector<int>& arr) 
{
  unordered_map<int, int> freq;
  
  for(int i = 0; i < arr.size(); ++i) 
   freq[arr[i]]++;
  
  priority_queue<int> pq;

  for(auto iter: freq) 
     pq.push(iter.second);
  
  int count = 0, res = 0;
  while(count < arr.size()/2) {
      res++;
      count += pq.top();
      pq.pop();
  }
  return res;
}
int main()
{
   vector<int> arr = {3,3,3,3,5,5,5,2,2,7};

    cout<<"The min set size is "<< get_min_set_size(arr)<<endl;
    return 0;
}

Output:

The min set size is 2