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: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

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)
		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
		removed_size = 0
		while removed < size // 2:
			(count, value) = heappop(max_heap)
			count = -count
			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]
		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)
		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


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
		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 = {}
		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]))
		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()
		for i in arr:
			counts[i] = counts.get(i, 0) + 1
		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)
		counts.sort(reverse=True)
		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)
		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)
		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


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 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]
		arr_tup = sorted(arr_tup, key=lambda x: -x[1])
		count = 0
		total = 0
		for item in arr_tup:
			total += item[1]
			print(item[0])
			count += 1
			if total >= n / 2:
				return count


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


import collections

class Solution:

	def minSetSize(self, arr: List[int]) -> int:
		minSizeToRemove = len(arr) // 2
		counter = collections.Counter(arr)
		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])
			if sum >= minSizeToRemove:
				break
		return len(minSet)


class Solution:

	def minSetSize(self, arr: List[int]) -> int:
		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 = 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:
		length = len(arr)
		counts = {}
		for num in arr:
			if num not in counts:
				counts[num] = 1
			else:
				counts[num] += 1
		descending = sorted(counts.values(), reverse=True)
		count = 0
		total = 0
		for num in descending:
			total += num
			count += 1
			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)
		l = 0
		r = len(ls) - 1
		res = 0
		items = 0
		for i in range(len(ls)):
			res += 1
			items += ls[i][0]
			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:
		counts = {}
		for (i, elem) in enumerate(arr):
			counts[elem] = 1 if elem not in counts else counts[elem] + 1
		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:
		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


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:
		h = [(val * -1, key) for (key, val) in list(Counter(arr).items())]
		heapify(h)
		num_int = 0
		count = 0
		while 2 * count * -1 < len(arr):
			(c, i) = heappop(h)
			count += c
			num_int += 1
		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:
		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)
		seen = set()
		count = 0
		while 2 * count * -1 < len(arr):
			(c, i) = heappop(h)
			count += c
			seen.add(i)
		return len(seen)


from collections import defaultdict

class Solution:

	def minSetSize(self, arr: List[int]) -> int:
		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]):
			tot -= v
			res += 1
			if tot <= n // 2:
				return res
		return n


class Solution:

	def minSetSize(self, arr: List[int]) -> int:
		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:
		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.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