You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

&nbsp;
Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.


Example 2:

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


&nbsp;
Constraints:


	2 &lt;= arr.length &lt;= 105
	arr.length is even.
	1 &lt;= arr[i] &lt;= 105


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n = len(arr)
        half = n // 2
        
        c = Counter(arr)
        s = 0
        ans = 0
        
        for num, occurances in c.most_common():
            s += occurances
            ans += 1
            if s >= half:
                return ans
        return ans
class Solution {
    public int minSetSize(int[] arr) {
        int size=arr.length;
        int deletedSize=0;
        int countIteration=0;
        Map<Integer,Integer> hashMap=new HashMap<>();
        Queue<Map.Entry<Integer,Integer>> queue=new PriorityQueue<>((a,b)->b.getValue()-a.getValue());
        
        for(int i=0;i<size;i++)
        {
            if(hashMap.get(arr[i])!=null)
               hashMap.put(arr[i],hashMap.get(arr[i])+1);
            else 
                hashMap.put(arr[i],1);
        }
        
        for(Map.Entry<Integer,Integer> entry:hashMap.entrySet())
        {
            queue.add(entry);
        }
        
        while(!queue.isEmpty())
        {
            int totalOccurence=queue.poll().getValue();
            deletedSize+=totalOccurence; 
            countIteration++;
            if(deletedSize>=size/2)
                return countIteration;
           
        }
        return countIteration;
    }
}
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        const int n=1e5+10 ;
        int a[n]={0} ;
        for(int i=0 ;i<arr.size() ;i++)
        {
            a[arr[i]]++ ;
        }
        priority_queue<int> maxh ;
        for(int i=0; i<n ;i++)
        {
            maxh.push(a[i]) ;
        }
        int sum=0 ;
        int count=0 ;

        while(sum<(arr.size()/2))
        {
            sum=sum+maxh.top() ;
            maxh.pop() ;
            count++ ;
        }
        return count ;

    }
};
var minSetSize = function(arr) {
  let halfSize = arr.length / 2;
  const numsCount = Object.values(getNumsCount(arr)).sort((a, b) => b - a); // get the frequencies in an array sorted in descending order
  let setSize = 0;
  if (numsCount[0] >= halfSize) return 1; // if the highest frequency is greater than or equal to half of the array size, then you already have your smallest set size of 1
  for (let i = 0; i < numsCount.length; i++) {
    let numCount = numsCount[i];
    if (halfSize > 0) {
      setSize++;
      halfSize -= numCount;
    } else {
      return setSize;
    };
  };
};

var getNumsCount = function (arr) {
  let eleCounts = {};
  for (let i = 0; i < arr.length; i++) {
    let num = arr[i];
    if (!eleCounts[num]) {
      eleCounts[num] = 1;
    } else {
      eleCounts[num]++;
    };
  };
  return eleCounts;
};
Reduce Array Size to The Half