Given an 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.
 
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 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.

Example 3:
Input: arr = [1,9]
Output: 1

Example 4:
Input: arr = [1000,1000,3,7]
Output: 1

Example 5:
Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

 
Constraints:

1 <= arr.length <= 10^5
arr.length is even.
1 <= arr[i] <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        

Solutions:
from heapq import *
from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        counter = Counter(arr)
        size = len(arr)
        
        # unique elements (remove half of them)
        if len(counter) == size:
            return (size - 1) // 2 + 1
        
        max_heap = [(-freq, value) for value, freq in list(counter.items())]
        heapify(max_heap)
        
        removed = 0  # number of elements removed
        removed_size = 0  # size of the remvoved set
        
        while removed < size//2:
            count, value = heappop(max_heap)
            count = -count  # change the count back to +ve
            removed += count
            removed_size += 1
        
        return removed_size
        
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        freq = Counter(arr)
        final_length = 0
        half = len(arr)/2
        reduce = 0
        for n, f in freq.most_common():
            final_length+=f
            reduce+=1
            if final_length>=half:
                return reduce

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counts=collections.Counter(arr)
        counts=[count for number,count in counts.most_common()]
        
        set_size=0
        tot=0
        for x in counts:
            tot+=x
            set_size+=1
            if tot>=(len(arr)//2):
                break
        return set_size


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        hash_map = collections.Counter(arr)
        hash_map = {k:v for k,v in sorted(hash_map.items(),key=lambda item: item[1])}
        total_size = len(arr)
        values = list(hash_map.values())[::-1]
        # print(values)
        ans=0
        i=0
        while total_size>len(arr)//2:
            total_size-=values[i]
            i+=1
            ans+=1
        return ans

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        N = len(arr)
        target = math.ceil(N/2)
        dic = collections.Counter(arr)
        lst = [(num,cnt) for num,cnt in dic.items()]
        lst.sort(key = lambda x: [-x[1],x[0]])
        
        ans = 0
        count = 0
        for num,cnt in lst:
            count += cnt
            ans += 1
            if count >= target:
                return ans
        return ans

from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        temp = sorted([(v, k) for k, v in list(cnt.items())])
        curr = 0
        for i in range(1, len(temp)+1):
            curr += temp[-i][0]
            if curr >= len(arr)/2:
                return i


from collections import defaultdict
from collections import OrderedDict
class Solution:
    
    def createCount(self,arr):
        res = defaultdict(lambda:0)
        for num in arr:
            res[num]+=1
        res = sorted(list(res.items()),key = lambda x:x[1],reverse = True)
        res = collections.OrderedDict(res)
        return res
    
    def minSetSize(self, arr: List[int]) -> int:
        total = 0
        num = 0
        res = self.createCount(arr)
        for key in res:
            if total>=len(arr)//2:
                return num
            total+=res[key]
            num+=1
            
        return num    
            
            
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        dic = {}
        n_arr = []
        res = 0
        length = len(arr)
        for i in arr:
            if i in list(dic.keys()):
                dic[i] += 1
            else:
                dic[i] = 1
        
        for i in dic:
            n_arr.append([dic[i], i])
        
        n_arr = sorted(n_arr)
        for i in range (len(n_arr) -1, -1, -1):
            length -= n_arr[i][0]
            res+=1
            if length <= len(arr)//2:
                break
        return res


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        L = len(arr)
        
        count = collections.Counter(arr)
        freq = sorted(count.values())
        size = 0
        res = 0
        
        for i in range(len(freq)-1, -1, -1):
            size += freq[i]
            res += 1
            if size >= L/2:
                return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        import math
        from collections import Counter
        a=Counter(arr)
        b=list(a.values())
        b.sort(reverse = True)
        n=len(arr)
        summ=0
        for i in range(len(b)):
            summ+=b[i]
            if summ>=int(math.floor(0.5*n)):
                return i+1
        return None

from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        freq = Counter(arr)
        h = []
        for num, freq in freq.items():
            print(num, freq)
            heappush(h, (-freq, num))
        count = 0
        ret = 0
        while count < (len(arr) // 2):
            count += -heappop(h)[0]
            ret += 1
        return ret

from collections import OrderedDict

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        fq = {}
        for i in arr:
            fq[i] = fq.get(i, 0) + 1
        sorted_m = OrderedDict(sorted(list(fq.items()), key=lambda k:(k[1], k[0]), reverse=True))
        
        sm = 0
        req = len(arr)//2 + len(arr)%2
        ans = 0
        for i in sorted_m:
            sm += sorted_m[i]
            ans += 1
            if sm>=req:
                break
        return ans



class Solution:
    def minSetSize(self, array: List[int]) -> int:
        hashMap = dict()
        for item in array:
            if item not in hashMap:
                hashMap[item] = 0
            hashMap[item] += 1
        

                
        length = len(array)
        itemToBeRemoved = 0
        halfOflength = len(array) // 2
        

        
        for value in sorted(list(hashMap.values()), reverse = True):
            length -= value
            itemToBeRemoved += 1
            if length <= halfOflength:
                return itemToBeRemoved


import collections
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        count = sorted(list(collections.Counter(arr).values()), reverse=True)
        toRemove = 0
        size = 0
        for c in count:
            toRemove += c
            size += 1
            if toRemove >= len(arr) / 2:
                break
        return size




class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = collections.Counter(arr)
        sums = [0 for i in range(len(counter))]
        curr = 0
        half = len(arr) // 2
        if len(arr) % 2 == 1:
            half += 1
        res = len(counter)
        for i, key in enumerate(sorted(counter.keys(), key=lambda x:counter[x], reverse=True)):
            curr += counter[key]
            if curr >= half:
                res = min(res, i + 1)
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        if len(set(arr))==1:
            return 1
        if len(set(arr))==len(arr):
            if len(arr)%2==0:
                return int(len(arr)/2)
            else:
                return (len(arr)//2) +1
        u=list(set(arr))
        d_u={}
        for ele in u:
            d_u[ele]= arr.count(ele)
            
        d_u=sorted(list(d_u.items()), key=lambda x: x[1], reverse=True)
        #print(d_u)
        s=0
        size=0
        for ele in d_u:
            size+=1
            s+= ele[1]
            if (s>= len(arr)/2) & (len(arr)%2==0):
                return size
            if (len(arr)%2==1) & (s>= (len(arr)//2+1) ):
                return size
            
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        half = len(arr) / 2
        counts = {}
        for val in arr:
            if val in counts.keys():
                counts[val] += 1
            else:
                counts[val] = 1
        count = 0
        included = 0
        for key in sorted(counts, key=counts.get, reverse=True):
            count += counts[key]
            included += 1
            if (count >= half):
                return included

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d={}
        for i in arr:
            if i not in d:
                d[i]=0
            d[i]+=1
        d=list(sorted(d.items(), key = lambda kv:kv[1],reverse=True))
        sum=0
        cnt=0
        for i in range(len(d)):
            if sum>=(len(arr)/2):
                break
            else:
                sum=sum+d[i][1]
                cnt+=1
        return cnt             

'''
Keep a dict of counts and add all of them to a heap. Then we remove from heap until size <= half and we return size of set that we have to remove
'''
from heapq import heapify, heappush, heappop
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counts = collections.Counter(arr)
        maxheap = []
        for i, freq in list(counts.items()):
            maxheap.append((-freq,i))
        heapify(maxheap)
        curN = len(arr)
        sol = 0
        while curN > len(arr) / 2:
            freq, cur = heappop(maxheap)
            curN += freq
            sol += 1
            
            
        return sol


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        half = len(arr)//2
        count = ans = 0
        counts = Counter(arr)
        
        for k, v in counts.most_common():
            ans += v
            count+=1
            if  ans >= half:
                return count


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n = len(arr)//2
        freq = {}
        for i in arr:
            if i in freq:
                freq[i] += 1
            else:
                freq[i] = 1
        res = [i for i in freq.values()]
        res.sort(reverse = True)
        total = 0
        count = 0
        for i in res:
            total += i
            count += 1
            if total >= n:
                return count

from collections import defaultdict
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = defaultdict(int)
        for a in arr:
            counter[a] += 1
        nums = list(counter.keys())
        nums.sort(key = lambda x: counter[x], reverse = True)
        count = 0
        total = 0
        half = (len(arr)+1) // 2
        for n in nums:
            total += counter[n]
            count += 1
            if total >= half: return count 

import collections
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = collections.Counter(arr)
        
        vals = sorted(list(d.values()),reverse=True)
        
        ans = 0
        s = 0
        for i in range(len(vals)):
            ans += 1
            s += vals[i]
            if s >= len(arr)//2:
                return ans


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        H ={}
        for x in arr:
            H[x]=H.get(x,0)-1
        L = list(H.values())
        heapq.heapify(L)
        t = 0
        a = 0
        # print(L)
        M = len(arr)//2
        while t < M:
            x = heapq.heappop(L)
            t+=(-x)
            a+=1
        return a
            
        
        


from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        temp = sorted(list(cnt.keys()), key = lambda x: cnt[x])
        curr = 0
        for i in range(1, len(temp)+1):
            curr += cnt[temp[-i]]
            if curr >= len(arr)/2:
                return i


import collections

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        freq = collections.Counter(arr)
        comp = [(freq[key],key) for key in freq]
        comp.sort(reverse=True)
        target = len(arr)/2
        index,curr_sum = 0,0
        while index < len(comp) and curr_sum < target:
            curr_sum += comp[index][0]
            index +=1
        return index

import numpy as np
import collections
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        dict_gens = collections.Counter(arr)
        generators = sorted(dict_gens.values())
        min_deactivate = np.ceil(len(arr)/2)
        turn_off = 0
        i = 1
        while turn_off < min_deactivate:
            turn_off += generators[-i]
            i += 1
        return i-1


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        if len(arr) == 0:
            return 0
        if len(arr) < 3:
            return 1
        
        counter = {}  # Could use defaultdict to save a few lines of code
        for n in arr:
            if n in counter:
                counter[n] += 1
            else:
                counter[n] = 1
        
        counts = sorted(counter.values())
        
        total_ints = len(arr)
        set_size = 0
        
        while total_ints > len(arr)//2:
            set_size += 1
            total_ints -= counts.pop()
        
        return set_size
                
                


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n, target = len(arr), len(arr)//2
        counts = {}
        for i in arr:
            if i in counts:
                counts[i] += 1
            else:
                counts[i] = 1
        
        counts = sorted(list(counts.values()), reverse=True)
        
        numRemoved = 0
        for i in counts:
            n -= i
            numRemoved += 1
            if n <= target:
                return numRemoved
        
        return numRemoved
        


class Solution:
    def minSetSize(self, arr) -> int:
        counter = {}
        for val in arr:
            if val not in counter:
                counter[val] = 0
            counter[val] += 1
        values = []
        for val in counter:
            values.append(counter[val])
        values.sort(reverse=True)

        total = 0

        nhalf = len(arr) // 2
        new_n = len(arr)
        i = 0
        while new_n > nhalf:
            total += 1
            new_n -= values[i]
            i += 1

        return total

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        length = len(arr)
        counter = {}
        for num in arr:
            try:
                counter[num] += 1
            except:
                counter[num] = 1
        
        array = sorted(list(counter.items()), key = lambda x:(-x[1], x[0]))
        # print(array)
        res = 0
        i = 0
        while res * 2 < length:
            res += array[i][1]
            i += 1
        return i

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        order = collections.Counter(arr).most_common()
        ans = 0
        sum = 0
        mid = len(arr)//2 if len(arr)%2==0 else (len(arr)//2 +1)
        for i,j in order:
            sum+=j
            ans+=1
            if sum >= mid:
                break
        return ans  


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = collections.Counter(arr)
        heap = [(-freq, num) for num, freq in list(counter.items())]
        heapq.heapify(heap)
        target = len(arr) // 2
        ans = len(heap)
        while target > 0:
            target += heapq.heappop(heap)[0]
        return ans - len(heap)
            


import collections
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        lst = []
        dic = collections.Counter(arr)
        keys = sorted(dic,key = lambda x: dic[x],reverse = True)
        
        for n in keys:
            if len(lst) >= len(arr)//2:
                return len(set(lst))
            else:
                for _ in range(dic[n]):
                    lst.append(n)
        
        if len(lst) >= len(arr)//2:
                return len(set(lst))

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counts = dict()
        # count all distinct values
        for i in arr:
            counts[i] = counts.get(i, 0) + 1
            
        #greedy solution
        #sort counts in desc order
        total_count=0        
        for index, count in enumerate(sorted(list(counts.values()), reverse=True)):
            total_count += count
            if total_count >= len(arr) // 2:
                return index + 1
        return 0


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        for num in arr:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        
        val = [d[i] for i in d]
        val.sort(reverse = True)
        
        count, total = 0,0
        for each in val:
            total += each
            count += 1
            if total >= len(arr)//2:
                break
        return count


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        
        counts = []
        current_run = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i - 1]:
                current_run += 1
                continue
            counts.append(current_run)
            current_run = 1
        counts.append(current_run)

        # Reverse sort the counts.
        counts.sort(reverse=True)

        # Remove numbers until at least half are removed.
        numbers_removed_from_arr = 0
        set_size = 0
        for count in counts:
            numbers_removed_from_arr += count
            set_size += 1
            if (numbers_removed_from_arr >= len(arr) // 2):
                break

        return set_size

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arrCounter = Counter(arr)
        sortedList = sorted([(key, arrCounter[key]) for key in arrCounter], key = lambda x:(-x[1], x))
        arrLen = len(arr)
        target = arrLen//2
        ans = 0
        for _, aNum in sortedList:
            arrLen -= aNum
            ans += 1
            if arrLen <= target:
                return ans


from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        half=len(arr)/2
        count=0
        dic=Counter(arr)
        for i in dic.most_common():
            half-=i[1]
            count+=1
            if half<=0:
                return count


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        length=len(arr)
        bar=length//2
        d={}
        for i in range(len(arr)):
            d[arr[i]]=d.get(arr[i],0)+1
        res=0
        l=list(sorted(d.values(),reverse=True))
        for value in l:
            length-=value
            res+=1
            if length<=bar:
                return res
        return res

from collections import Counter
class Solution:
    
    def minSetSize(self, arr: List[int]) -> int:
        counts = Counter(arr)
        elements = 0
        count = len(arr) / 2
        for (key, value_count) in sorted(list(counts.items()), key=lambda x: x[1], reverse=True):
            if count <= 0:
                break
            elements += 1
            count -= value_count
        return elements


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        objective = len(arr)//2
        res = ret = 0
        c = collections.Counter(arr)
        for k, v in c.most_common():
            res += v
            ret += 1
            if res >= objective:
                break
        return ret

from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        c = Counter(arr)
        
        a, res = 0, 0
        for n, c in c.most_common():
            a += c
            res += 1
            if a >= len(arr) // 2:
                break
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n = len(arr)
        count = Counter(arr)
        res = 0
        s = 0
        for key, rep in count.most_common():
            s += 1
            res += rep
            if res >=n//2 :
                return s
            


class Solution:
    def minSetSize(self, arr: List[int]) -> int:

        cnter = collections.Counter(arr).most_common()
        counting = 0
        for i, blep in enumerate(cnter):
            if counting + blep[1] >= len(arr)/2:
                return i + 1
            else:
                counting += blep[1]
            


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        c=Counter(arr)
        c=list(c.values())
        c.sort(reverse=True)
        k=len(c)//2
        s=0
        count=0
        for i in range(len(c)):
            s+=c[i]
            count+=1
            if s>=len(arr)//2:
                return count
            
            
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        from collections import Counter
        count = 0
        ans = 0
        c = Counter(arr)
        target = len(arr)/2
        for k,v in sorted(list(c.items()), key=lambda x: x[1], reverse=True):
            count+=v
            ans+=1
            if count >= target: return ans
        return 0


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        c=collections.Counter(arr)
        n=len(arr)
        res=0
        count=0
        for c,v in c.most_common():
            count+=v
            res+=1
            if count>=n//2:
                break
        
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        for k in arr:
            if k in d:
                d[k] += 1
            else:
                d[k] = 1
                
        t = []
        for k, v in d.items():
            t.append(v)
        t.sort(reverse=True)
        r = 0
        ii = 0
        while r < len(arr)//2 + len(arr)%1 :
            r += t[ii]
            ii+=1
        return ii

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        num = {}
        
        for i in arr:
            if i in num:
                num[i] += 1
            else:
                num[i] = 1
        
        sort_nums = sorted(num.items(), key=lambda x: x[1], reverse=True)
        
        total = 0
        ind = 0
        
        for i in sort_nums:
            if total < len(arr) / 2:
                total += i[1]
                ind += 1
            else:
                break
        
        return ind

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        ans=0
        d={}
        l=[]
        res=0
        for i in arr:
            if i in d:
                d[i]+=1
            else:
                d[i]=1
        for i in d:
            l.append(d[i])
        l.sort(reverse=True)
        print(l)
        for i in range(len(l)):
            res+=l[i]
            if res>=(len(arr)//2):
                return i+1


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        A = {}
        for x in arr:
            A[x] = A.get(x,0) + 1
        
        p = 0 
        count = 0 
        for x in sorted(list(A.items()), key = lambda x: -x[1]):
            p += x[1]
            count += 1
            if p >= len(arr) // 2:
                return count 
        
                

    
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        dic = {}
        for num in arr:
            dic[num] = dic.get(num, 0) + 1

        array = [v for k, v in sorted(list(dic.items()), key=lambda item: item[1], reverse=True)]

        target = len(arr)/2

        current, i = 0, 0
        for num in array:
            i += 1
            current += num
            if current >= target:
                return i


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = dict()
        for x in arr:
            d.setdefault(x, 0)
            d[x] += 1
        c = sorted(d.values(), reverse=True)
        for i in range(1, len(c)):
            c[i] += c[i-1]
        
        for i, x in enumerate(c):
            if x >= len(arr) // 2:
                return i + 1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n = len(arr)
        counter = collections.Counter(arr)
        cur = 0
        ans = 0
        for num in sorted(list(counter.values()) ,reverse = True):
            cur += num
            ans += 1
            if cur >= n//2:
                return ans


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        mem = {}
        for i in arr:
            if i in mem:
                mem[i]+=1
            else:
                mem[i]=1
        
        sorted_array = sorted(list(mem.values()), reverse=True)
        counter = 0
        res = 0
        print(sorted_array)
        for i in sorted_array:
            res +=i
            counter += 1
            print(res)
            if res>=len(arr)/2:
                
                return counter
        
            
        
        
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d={}
        for i in arr:
            if i in list(d.keys()):
                d[i]+=1
            else:
                d[i]=1
        s= len(arr)
        ans=0
        for j in sorted(list(d.items()),key=lambda x:x[1],reverse=True):
            s-=j[1]
            ans+=1
            if s<=(len(arr)//2):
                return ans
            else:
                continue
        
            


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        tmp_dict = {}
        for e in arr:
            if e not in tmp_dict:
                tmp_dict[e] = 1
            else:
                tmp_dict[e] += 1
        tmp = [(key,tmp_dict[key]) for key in tmp_dict]
        tmp.sort(key=lambda x:x[1],reverse=True)
        res = []
        cur = 0
        i = 0
        while cur<len(arr)//2:
            res.append(tmp[i][0])
            cur += tmp[i][1]
            i += 1
        return len(res)
            


from collections import Counter
class Solution:
    def minSetSize(self, arr) -> int:
        counterArr = [0] * (len(arr) + 1)
        for value in Counter(arr).values():
            counterArr[value] += 1
        steps = 0
        total = 0
        print(counterArr)
        for i in reversed(range(len(arr) + 1)):
            num = counterArr[i]
            for j in range(num):
                total += i
                steps += 1
                if total >= len(arr) // 2:
                    return steps
        return steps

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        occ = {}
        for num in arr:
            if num in occ:
                occ[num] += 1
            else:
                occ[num] = 1

        occ_lst = list(occ.items())
        occ_lst.sort(key=lambda x: x[1], reverse=True)
        total_elems_removed = 0
        removal_set_size = 0
        for i, (_, num_occur) in enumerate(occ_lst):
            total_elems_removed += num_occur
            if total_elems_removed >= math.ceil(len(arr) / 2.0):
                return i + 1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        h = {}
        for i in arr:
            if not i in h:
                h[i] = 0
            h[i] += 1
            
        v = sorted(list(h.values()),reverse = True)
        m = len(arr)
        t = 0
        p = 0
        i = 0
        print(v)
        while t < m//2:
            t += v[i]
            i+=1
            p+=1
            
        return p


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        d = {}
        n = len(arr)
        
        for a in arr:
            d[a] = d.get(a,0) + 1
        
        val  = sorted(list(d.items()), key = lambda x :x[1])[::-1]
        
        count =0
        
        for i,(_,val_i) in enumerate(val):
            count += val_i
            print(count)
            if count>=n//2:
                return i +1
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        dict_freq = {}
        
        for i in range(len(arr)):
            if arr[i] in dict_freq:
                dict_freq[arr[i]] += 1
            else:
                dict_freq[arr[i]] = 1
                
        target_size = len(arr)//2
        sort_dict = dict(sorted(list(dict_freq.items()), key=lambda x: x[1], reverse=True))
        print(sort_dict)
        for i in dict_freq:
            
            if dict_freq[i] >= target_size:
                
                return 1
            else:
                break
        cnt = 0 
        count = 0
        for i in sort_dict:
            cnt = cnt + sort_dict[i]
            count = count+1
            if cnt >= target_size:
                return count
                
        return 8
            
            


from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        countOfArray = Counter(arr)
        listOfValues = list(countOfArray.values())
        listOfValues.sort(reverse = True)
        lenOfArray = len(arr)
        halfTheLength = lenOfArray//2
        ret = 0
        for val in listOfValues:
            lenOfArray = lenOfArray - val
            ret += 1
            if lenOfArray <= halfTheLength :
                break
        return ret

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        if len(set(arr)) == 1:
            return 1
        maps = {x:0 for x in set(arr)}
        for x in arr:
            maps[x]+=1
        maps  = sorted(list(maps.items()), key=lambda x: x[1], reverse=True)
        mincount = len(arr)//2
        ans = 0
        currLength,sub = len(arr),9
        # print(maps)
        for x in range(len(maps)):
            key,val = maps[x]
            if currLength > mincount:
                currLength -= val
                ans += 1
            else:
                return ans




class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr_len = len(arr)
        # arr_int = list(set(arr))
        int_dict={}
        val=[]
        for i in arr:
            int_dict[i] = int_dict.setdefault(i,0) + 1
        
        for i in int_dict:
            val.append(int_dict[i])
        val.sort()
        
        count_num=0
        loc=0
        for i in val[::-1]:
            count_num+=i
            loc+=1
            if count_num>=arr_len/2:
                break
        return loc
        # if len(set(arr)) == arr_len:
        #     return int(arr_len+0.5)
        # else:


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        c = Counter(arr)
        result = list()
        count = 0
        for k,v in sorted(c.items(),key = lambda item: item[1],reverse=True):
            if count < len(arr)//2:
                result.append(k)
                count += v
        return len(result)

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        d = {}
        n = len(arr)
        
        for a in arr:
            d[a] = d.get(a,0) + 1
        
        val  = sorted(list(d.items()), key = lambda x :x[1])[::-1]
        
        count =0
        
        for i,(_,val_i) in enumerate(val):
            count += val_i
            
            if count>=n//2:
                return i +1
        


class Solution:
    def floor_counter(self,n):
      if n%2==0:
        return n/2
      else:
        return (n+1)/2
    def minSetSize(self, arr: List[int]) -> int:
      ceiling = self.floor_counter(len(arr))
      freq = {}
      for elem in arr:
        if elem in freq:
          freq[elem] += 1
        else:
          freq[elem] = 1
      sorted_freq = sorted(freq.items(), key=lambda k:k[1], reverse=True)
      sum = 0
      type_counter = []
      for i in range(len(sorted_freq)):
        sum +=(sorted_freq[i][1])
        print(sum)
        type_counter.append(sorted_freq[i][0])
        if sum>=ceiling:
          return len(type_counter)

from collections import defaultdict

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        occurances = defaultdict(int)
        
        for num in arr:
            occurances[num] += 1
          
        dictlist = []
        for key, value in occurances.items():
            temp = [key,value]
            dictlist.append(temp)
    
        dictlist = sorted(dictlist, key=lambda x: x[1])

        
        count = 0
        removals =0
        while (count < len(arr) / 2):
            count += dictlist[-1][1] 
            dictlist.pop()
            removals +=1 
        
        return removals

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        n = len(arr)
        arr_map = Counter(arr)
        arr_tup = [(item, arr_map[item]) for item in arr_map]
        #print(arr_tup)
        arr_tup = sorted(arr_tup, key= lambda x : -x[1]) #Decrementing based on frequency
        #print(arr_tup)
        count = 0
        total = 0
        for item in arr_tup:
            total += item[1] #Counting max freq
            print((item[0]))
            count += 1
            if total >= n/2:
                return count
        
    ''' n = len(arr)
        
        freq = {}
        for i in arr:
            if i in freq:
                freq[i] += 1
            else:
                freq[i] = 1
                
        new_set = set()
                
        max_freq = max(freq, key = freq.get)
        del(freq[max_freq])
        
        new_set.add(max_freq)
        
        arr = [val for val in arr if val != max_freq]
        
        while True:
            
            if len(arr) <= n//2:
                return len(new_set)
            else:
                max_freq = max(freq, key = freq.get)
                del(freq[max_freq])
                new_set.add(max_freq)
                arr = [val for val in arr if val != max_freq]'''
                
                
                


from collections import *
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = Counter()
        for num in arr:
            d[num] += 1
        
        counts = list(d.values())
        
        counts.sort(reverse=True)
        
        total = 0
        for (i,count) in enumerate(counts):
            total += count
            if total >= len(arr)//2:
                return i+1
        
        return None # should never reach here

import collections

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        minSizeToRemove = len(arr) //2
        # print(minSizeToRemove)
        counter = collections.Counter(arr)
        # print(counter)
        sortedCounters = sorted(counter.items(), key=lambda x: x[1], reverse=True)
        sum = 0
        minSet = set()
        for i in sortedCounters:
            
            sum+=i[1]
            minSet.add(i[0])
            # print(i[0], i[1], sum, minSet)
            if sum >= minSizeToRemove:
                break
            
        return len(minSet)

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
#         if not arr:
#             return 0
        
#         ceil = len(arr) / 2.0
        
#         count = collections.Counter(arr)
#         sort = count.most_common()
#         sum = 0
#         for idx,val in enumerate(sort):
#             sum += val[1]
#             if sum >= ceil:
#                 return idx+1
            
#         return idx+1
        if not arr:
            return 0
        counter = collections.Counter(arr)
        max_val = max(counter.values())
        
        buckets = [0] * (max_val+1)
        
        for count in list(counter.values()):
            buckets[count] += 1
            
        set_size = 0
        arr_num_to_remove = len(arr) // 2
        bucket = max_val
        
        while arr_num_to_remove > 0:
            max_need_from_bucket = math.ceil(arr_num_to_remove / bucket)
            set_size_increase = min(buckets[bucket],max_need_from_bucket)
            set_size += set_size_increase
            arr_num_to_remove -= set_size_increase * bucket
            bucket -= 1
            
        return set_size
    


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        numberDict = {}
        
        for i in range(len(arr)):
            
            if arr[i] not in numberDict:
                numberDict[arr[i]] = 1
            else:
                numberDict[arr[i]] += 1
                
        sortedOrders = sorted(list(numberDict.items()), key=lambda x: x[1], reverse=True)
        
        total = 0
        setSize = 0
        for i in sortedOrders:
            
            
            if total >= (len(arr)//2):
                return setSize
            
            total += i[1]
            setSize += 1
        
        
        return setSize


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
#         total_count = len(arr)
#         values = set(arr)
#         values = list(values)
#         possible_combinations = []
        
#         for i in values:
#             possible_combinations.append([i,arr.count(i)])
        
#         result = [seq for i in range(len([item[1] for item in possible_combinations]), 0, -1) for seq in itertools.combinations([item[1] for item in possible_combinations], i) if sum(seq) >= total_count//2]
        
        
#         return min(len(i) for i in result)
    
    
        total_count = 0
        arr_mc = collections.Counter(arr).most_common()
        
        print(arr_mc)
        
        for i in range(len(arr_mc)):
            total_count += arr_mc[i][1]
            if total_count >= len(arr)/2:
                return i + 1
        
            
            
            
        
        
        
        


from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        sz = len(arr)
        d = sorted(list(Counter(arr).items()), key=lambda x: -x[1])
        num = 0
        numElems = 0
        for e in d:
            numElems += e[1]
            if numElems < sz//2:
                num += 1
            else:
                return num+1


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        n = len(arr)
        for num in arr:
            if num not in d:
                d[num] = 0
            d[num] += 1
        num_freq = list(sorted([v for k,v in d.items()]))
        tot = 0
        m = len(num_freq)
        i = 0
        
        while(tot < n/2 and i<m):
            tot += num_freq[m-i-1]
            i+=1
            print(i)
        print(num_freq)
        return i

class Solution:
    
    def check(self, arr, to_remove):
        return len(tuple(filter(lambda x: not to_remove.contains(x), arr))) <= len(arr) / 2
    
    def minSetSize(self, arr: List[int]) -> int:
        all_nums = set(arr)
        freq = {n:0 for n in all_nums}
        for num in arr:
            freq[num] += 1
            
        nums_by_count = sorted(freq.items(), key=lambda x: x[1], reverse=True)
        remove_count = 0
        result = 0
        half = len(arr) / 2
        for item in nums_by_count:
            num, count = item
            remove_count += count
            result += 1
            if remove_count >= half:
                return result

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        dict_={}
        for num in arr:
            if num not in dict_:
                dict_[num]=1
            else:
                dict_[num]+=1
                
        sort_list = sorted(dict_.keys(),key=lambda x: dict_[x],reverse=True)
        
        n = len(arr)
        size = 0
        for num in sort_list:
            n-=dict_[num]
            size+=1
            if n<len(arr)//2+1:
                return size

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # get length of array 
        length = len(arr)
        # build dict to count how many times each int appears
        counts = {}
        for num in arr:
            if num not in counts:
                counts[num] =1
            else:
                counts[num] += 1
                
        # print(counts)
        
        # get values from dict, sort in descending order
        descending = sorted(counts.values(), reverse =  True)
        # print(descending)
        # initialize 2 variables: count and total
        count = 0
        total = 0
        # loop over descending list of counts
        for num in descending:
            # add each number to our total
            total += num
            # increment count by 1
            count += 1
            # if our total is half or more, return count
            if total >= length/2:
                return count

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        from collections import Counter
        
        c = Counter (arr)
        
        ls = []
        for i, c in c.items ():
            ls .append ((c, i))
            
        ls.sort (reverse=True)
        #print (ls)
        
        l = 0
        r = len (ls)-1
        
        res = 0
        items = 0
        
        for i in range (len(ls)):
            res += 1
            items += ls[i][0]
            #print (items)
            if items >=  (len(arr)//2):
                break
                
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        freq=[]
        k=0
        while k<len(arr):
            j=k+1
            fr=1
            while j<len(arr):
                if arr[j]==arr[k]:
                    fr+=1
                else:
                    break
                j+=1
                k+=1
            freq.append(fr)
            k+=1
        freq.sort()
        freq.reverse()
        k=0
        no=0
        count=0
        while k<len(freq) and count<len(arr)/2:
            if freq[0]>=len(arr)/2:
                no+=1
                break
            count=count+freq[k]
            no+=1
            k+=1
        return no
            


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # get counts of each element
        counts = {}
        for i, elem in enumerate(arr):
            counts[elem] = 1 if elem not in counts else counts[elem]+1
        # keep getting max and checking if the length is less than half upon removal until it is
        size = len(arr)
        count = 0
        vals = sorted(counts.values(),reverse=True)
        while size > len(arr)/2:
            maxElem = vals[count]
            size -= maxElem
            count += 1
        return count

import math
from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        curr = len(arr)
        target = math.ceil(len(arr) / 2)
        ans = 0
        
        counts = Counter(arr)
        
        for count in sorted(list(counts.values()), reverse=True):
            curr -= count
            ans += 1
            
            if curr <= target:
                return ans


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # get the most freq occurring ints 
        d = {}
        for a in arr:
            if a in d:
                d[a] += 1
            else:
                d[a] = 1
        
        q = []
        for k in d:
            heappush(q, (-d[k], k))
        
        size = len(arr)
        half = len(arr) / 2
        numPop = 0
        while size > half:
            poped = heappop(q)
            size += poped[0]
            numPop += 1
        
        return numPop

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        targetLen = len(arr) / 2
        elementsRemoved = depth = 0
        
        data = collections.Counter(arr)
        
        for key, val in data.most_common():
            elementsRemoved += val
            depth += 1
            
            if elementsRemoved >= targetLen:
                return depth
            
            


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        half = len(arr) // 2
        d = {}
        for num in arr:
            if num not in d:
                d[num] = 0
            d[num] += 1
        
        lst = sorted(list(d.values()), reverse=True)
        
        accum = 0
        res = 0
        for item in lst:
            if accum < half:
                accum += item
                res += 1
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = collections.defaultdict(int)
        for i in arr:
            d[i] += 1
        res = len(arr)
        orig = len(arr)
        count = 0
        
        freq = [(d[i],i) for i in d]
        freq.sort(reverse=True)
        count = 0
        for i in freq:
            res -= i[0]
            count+= 1
            if res <= orig//2:
                return count
        return -1

from collections import defaultdict
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        count_map = defaultdict(int)
        for num in arr:
            count_map[num] += 1
        
        
        res_arr = []
        for num, count in count_map.items():
            res_arr.append((count, num))
        
        res_arr = sorted(res_arr)[::-1]
        
        count = 0
        index = 0
        while count < len(arr) // 2:
            count += res_arr[index][0]
            index += 1
        
        return index

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        halfLength = len(arr)//2
        valDict = {}
        for val in arr:
            if val in valDict:
                valDict[val] += 1
            else:
                valDict[val] = 1

        setSize = 0
        lengthValsRemoved = 0
        for val in sorted(valDict.values(), reverse=True):
            setSize += 1
            lengthValsRemoved += val
            if lengthValsRemoved >= halfLength:
                break

        return setSize

from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        n = len(arr)
        counts = Counter(arr)
        sorted_counts = sorted(counts.items(), key=lambda x: (-x[1], x[0]))
        count = 0
        ans = 0
        for sc in sorted_counts:
            count += sc[1]
            ans += 1
            if count >= n//2:
                return ans
        return ans

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        frequency = defaultdict(int)
        for num in arr:
            frequency[num] += 1
        arrLength = len(arr)
        pairs = []
        for key,val in frequency.items():
            pairs.append((val,key))
        pairs.sort(reverse = True)
        cumSum = 0
        for counter,pair in enumerate(pairs):
            frequency,key = pair
            cumSum += frequency
            if cumSum >= arrLength/2:
                return counter+1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        countOfArray = Counter(arr)
        listOfValues = list(countOfArray.values())
        listOfValues.sort(reverse = True)
        lenOfArray = len(arr)
        halfTheLength = lenOfArray//2
        ret = 0
        for val in listOfValues:
            lenOfArray = lenOfArray - val
            ret += 1
            if lenOfArray <= halfTheLength :
                break
        return ret

from math import ceil
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        brr = []
        count = 1
        cur = arr[0]
        for i in range(1,len(arr)):
            if cur == arr[i]:
                count += 1
            else:
                brr.append([cur,count])
                cur = arr[i]
                count = 1
        brr.append([cur,count])
        brr.sort(key = lambda x:x[1],reverse = True)
        temp = 0
        temp1 = 0
        
        for i in brr:
            if temp >=ceil(len(arr)/2):
                return temp1
            temp1 += 1
            temp += i[1]
        return 1
            
        


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        numsdict = {}
        for i in arr:
            numsdict[i] = numsdict.get(i,0) + 1
        
        sortarr = sorted(numsdict.items(), key = lambda x: -x[1])
        
        count = 0
        i = 0

        while 2*count < len(arr):
            count += sortarr[i][1]
            i += 1
            
        return i

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = collections.defaultdict(int)
        for i in arr:
            d[i] += 1
        s = sorted([(d[i],i) for i in d],reverse=True)
        res = 0
        ans = 0
        for i,v in s:
            res += i
            ans += 1
            if res >= (len(arr) + 1) // 2: return ans
        return len(d)

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        c = Counter(arr)
        l = len(arr)
        tup = c.most_common(len(c))
        i = 0
        while l > len(arr)/2:
            l -= tup[i][1]
            i += 1
            
        return i


import numpy as np
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        n = len(arr)
        dict_model = {}
        for it in arr:
            if it in dict_model.keys():
                dict_model[it] += 1
            else:
                dict_model[it] = 1
        min_deactivate = np.ceil(n/2)
        generators = list(dict_model.values())
        generators.sort()
        turn_off = 0
        i = 1
        while turn_off < min_deactivate:
            turn_off += generators[-i]
            i += 1
        return i-1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        if not arr: return 0
        int_freq = collections.Counter(arr)
        size = len(arr)
        cur_size = size
        
        count = 0
        for num, freq in int_freq.most_common():
            cur_size -= freq
            count += 1
            if cur_size <= size // 2:
                return count

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # L, C = len(arr), collections.Counter(arr)
        # S = sorted(C.values(), reverse = True)
        # T = itertools.accumulate(S)
        # for i,v in enumerate(T):
        #     if v >= len(arr)//2: return i + 1
        
        
        
        h = [(val*(-1),key) for key,val in list(Counter(arr).items())]
        heapify(h)
        #print(h)
        num_int = 0
        count = 0
        while 2*count*(-1) < len(arr):
            c,i = heappop(h)
            count += c
            num_int +=1
            #print(seen)
        return num_int


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        l=len(arr)
        s=0
        
        cnt= Counter(arr)
        cnt= [j for i,j in cnt.items()]
        cnt.sort(reverse=True)
        for ind,i in enumerate(cnt):
            s+=i
            if s>=l//2:
                break
        return ind+1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # L, C = len(arr), collections.Counter(arr)
        # S = sorted(C.values(), reverse = True)
        # T = itertools.accumulate(S)
        # for i,v in enumerate(T):
        #     if v >= len(arr)//2: return i + 1
        
        
        
        dic = Counter(arr)
        h = [(val*(-1),key) for key,val in list(dic.items())]
        heapify(h)
        #print(h)
        num_int = 0
        count = 0
        while 2*count*(-1) < len(arr):
            c,i = heappop(h)
            count += c
            num_int +=1
            #print(seen)
        return num_int


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        n,half = len(arr), len(arr) // 2
        seen = set()
        for i in arr:
            d[i] = d.get(i,0) + 1
        d = sorted(d.items(), key=lambda x: -x[1])
        for k,v in d:
            if n - v > half:
                n -= v
                seen.add(k)
            else:
                seen.add(k)
                return len(seen)

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        h = {}
        for el in arr:
            if el not in h:
                h[el] = 0
            h[el] += 1
        
        tmp = []
        for key in list(h.keys()):
            tmp.append(h[key])
        
        tmp.sort()
        
        count = 0
        size = 0
        for i in range(len(tmp) - 1, -1, -1):
            size += tmp[i]
            count += 1
            if size >= math.ceil(len(arr) / 2):
                break
            
        
        return count


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        dic = Counter(arr)
        h = [(val*(-1),key) for key,val in list(dic.items())]
        heapify(h)
        #print(h)
        seen = set()
        count = 0
        while 2*count*(-1) < len(arr):
            c,i = heappop(h)
            count += c
            seen.add(i)
            #print(seen)
        return len(seen)


from collections import defaultdict
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # we will store the frequency of all the elements in a dictionary and from the dictionary we will pick the ones with the maximum value and remove them till we do not get half size
        # we keep two dictionaries ones from number to their frequency and another from frequency to number for better manipulation
        num_fre = defaultdict(int)
        fre_num = defaultdict(set)
        for i in range(len(arr)):
            num_fre[arr[i]] += 1
            fre_num[num_fre[arr[i]]].add(arr[i])
            if fre_num[num_fre[arr[i]] - 1] != set():
                fre_num[num_fre[arr[i]] - 1].remove(arr[i])
        
        del num_fre
        answer = set()
        removed_elements = 0
        for fre in sorted(fre_num.keys(),reverse = True):
            for element in fre_num[fre]:
                if removed_elements < len(arr) // 2:
                    removed_elements += fre
                    answer.add(element)
                else:
                    break
        return len(answer)

from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        tot = n = len(arr)
        count = Counter(arr)
        res = 0
        for k, v in sorted(count.items(), key=lambda x: -x[1]):
            # print(k,v)
            tot -= v
            res += 1
            if tot <= n // 2:
                return res
        return n

from collections import defaultdict
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # we will store the frequency of all the elements in a dictionary and from the dictionary we will pick the ones with the maximum value and remove them till we do not get half size
        # we keep two dictionaries ones from number to their frequency and another from frequency to number for better manipulation
        num_fre = defaultdict(int)
        fre_num = defaultdict(set)
        for i in range(len(arr)):
            num_fre[arr[i]] += 1
            fre_num[num_fre[arr[i]]].add(arr[i])
            if fre_num[num_fre[arr[i]] - 1] != set():
                fre_num[num_fre[arr[i]] - 1].remove(arr[i])
        
        answer = set()
        removed_elements = 0
        for fre in sorted(fre_num.keys(),reverse = True):
            for element in fre_num[fre]:
                if removed_elements < len(arr) // 2:
                    removed_elements += fre
                    answer.add(element)
                else:
                    break
        return len(answer)

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # count = Counter(arr)
        # count = sorted(count.items(), key=lambda item: item[1], reverse=1)
        # total = len(arr)
        # i = 0
        # res = set()
        # while total > len(arr) // 2:
        #     total -= count[i][1]
        #     res.add(count[i][0])
        #     i += 1
        # return res
        count = sorted(Counter(arr).values(), reverse=1)
        target = (len(arr)) // 2
        res = curr = 0
        for val in count:
            curr += val
            res += 1
            if curr >= target:
                break
        return res

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        N = len(arr)
        count = collections.Counter()
        for n in arr:
            count[n] += 1
        
        sorted_count = sorted(list(count.keys()), key=lambda c: count[c], reverse=True)
        removed_count = 0
        res = 0
        for c in sorted_count:
            removed_count += count[c]
            res += 1
            if removed_count >= (N + 1) // 2:
                break
        return res


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        h = []
        for num in arr:
            if num not in d:
                d[num] = 1
            else:
                d[num] += 1
                
        for k, v in list(d.items()):
            h.append((-v, k))
            
        heapq.heapify(h)
        
        ans = 0
        count = 0
        while count < len(arr)//2:
            v, k = heapq.heappop(h)
            count -= v
            ans += 1
            
        return ans
                


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        freqs = Counter(arr)
        
        sorted_freqs = sorted(list(freqs.items()), key = lambda x : x[1], reverse=True)
        
        print(sorted_freqs)
        
        half_len = len(arr) / 2
        
        current_len = 0
        res = 0
        
        for (i, j) in sorted_freqs:
            res += 1
            current_len += j
            if current_len >= half_len:
                return res


class Solution:
    def minSetSize(self, a: List[int]) -> int:
        d={}
        n=len(a)//2
        for i in a:
            if (i not in d):
                d[i]=1
            else:
                d[i]+=1
        d=sorted(d.items(),key=lambda x:x[1], reverse=True)
        print(d)
        sum=0
        count=0
        for i in d:
            x=i[1]
            sum+=x
            count+=1
            if(sum>=n):
                break
        return count

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        hashMap = dict()
        for item in arr:
            if item not in hashMap:
                hashMap[item] = 0
            hashMap[item] += 1
        
                
        length = len(arr)
        itemToBeRemoved = 0
        halfOflength = len(arr) // 2
        
        for value in sorted(list(hashMap.values()), reverse = True):
            length -= value
            itemToBeRemoved += 1
            if length <= halfOflength:
                return itemToBeRemoved


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
      counter = {}
      for num in arr:
        if num in counter:
          counter[num] += 1
        else:
          counter[num] = 1
      
      heap = []
      
      for num in list(counter.keys()):
        heapq.heappush(heap, (-counter[num], num))
                       
      n = len(arr)
      i = 0
      cumSum = 0
      while i < n and cumSum < n//2:
        freq, num = heapq.heappop(heap)
        cumSum += abs(freq)
        i+=1
      
      return i


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        checked, answer = [],0
        count_d,total = [],0
        
        if len(arr) == len(set(arr)):
            return int(len(arr)/2)
        
        for num in arr:
            if num not in checked:
                count_d.append(arr.count(num))
                checked.append(num)
        
        #count_d = sorted(count_d.items(), key=operator.itemgetter(1))
        count_d.sort()
        
        for d in range(1, len(count_d)+1):
            total += count_d[-d]
            answer += 1
            if total >= len(arr)/2:
                return answer

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        
        for el in arr:
            if d.get(el): d[el] += 1
            else: d[el] = 1
                
        s = sorted(d.values())
        l = len(arr) / 2
        c = 0
        
        for i in reversed(range(len(s))):
            l -= s[i]
            c += 1
            if l <= 0: break
                
        return c

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        numsdict = {}
        for i in arr: numsdict[i] = numsdict.get(i,0) + 1
        sortarr = sorted(numsdict.values(), reverse = True)
        
        count = 0
        i = 0

        while 2*count < len(arr):
            count += sortarr[i]
            i += 1
            
        return i

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        d = {}
        for i in arr:
            if i in d:
                d[i]+=1
            else:
                d[i] = 1
        d = sorted(d.items(), key = lambda x:x[1], reverse=True)
        print(d)
        total, count = 0, 0
        for i in d:
            total += i[1]
            count+=1
            if total >= len(arr)//2:
                return count