Given an array of items, the i'th index element denotes the item id’s and given a number m, the task is to remove m elements such that there should be minimum distinct id’s left. Print the number of distinct id’s.
Example 1 -
Input:
n = 6
arr[] = {2, 2, 1, 3, 3, 3}
m = 3
Output:
1
Explanation : 
Remove 2,2,1
Example 2 -
Input:
n = 8
arr[] = {2, 4, 1, 5, 3, 5, 1, 3}
m = 2
Output:
3
Explanation:
Remove 2,4
Your Task:
This is a function problem. You don't have to take any input. Your task is to complete the distinctIds() which takes sorted array, its size n, and m as its parameter. You only need to find the minimum number of distinct IDs and return it. The driver code will print the returned value.
Expected Time Complexity: O(n log(n))
Expected Auxillary Space: O(n)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{6}
1 ≤ m ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def distinctIds(self,arr : list, n : int, m : int):
        # Complete this function

Solutions:
from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		mp = defaultdict(int)
		count = 0
		for i in arr:
			mp[i] += 1
		a = list()
		for (key, value) in mp.items():
			a.append(value)
		a.sort()
		sz = len(a)
		for i in a:
			if i <= m:
				m -= i
				count += 1
			else:
				break
		return sz - count


from collections import OrderedDict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		table = {}
		count = 0
		for i in arr:
			if i in table:
				table[i] += 1
			else:
				table[i] = 1
				count += 1
		values = list(table.values())
		values.sort()
		for i in values:
			if m - i >= 0:
				m = m - i
				count -= 1
			else:
				return count
		return count


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		freq = defaultdict(int)
		for item in arr:
			freq[item] += 1
		sorted_freq = sorted(freq.items(), key=lambda x: x[1])
		count = len(freq)
		for (item, f) in sorted_freq:
			if m >= f:
				m -= f
				count -= 1
			else:
				break
		return count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		lst = list(d.values())
		lst.sort()
		for i in range(len(lst)):
			if m == 0:
				return len(lst) - i
				break
			if m < 0:
				return len(lst) - i + 1
				break
			m -= lst[i]
		if m >= 0:
			return 0
		else:
			return 1


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		if n <= m:
			return 0
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = list(d.values())
		l.sort()
		i = 0
		while i < n:
			if m - l[i] < 0:
				return len(l) - i
			elif m - l[i] == 0:
				return len(l) - i - 1
			m -= l[i]
			i += 1
		return 0


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		count = Counter(arr)
		count = sorted(count.items(), key=lambda x: x[1], reverse=True)
		while count and count[-1][1] <= m:
			m -= count.pop()[1]
		return len(count)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		rec = Counter(arr)
		lst = sorted(rec.values(), reverse=True)
		while lst and m > 0:
			if lst[-1] <= m:
				m -= lst.pop()
			else:
				break
		return len(lst)
from collections import Counter


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		freq = {}
		d = []
		count = 0
		for i in range(n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
		for i in freq:
			d.append([freq[i], i])
		d.sort()
		size = len(d)
		for i in range(size):
			if d[i][0] <= m:
				m -= d[i][0]
				count += 1
			else:
				return size - count
		return size - count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = len(d)
		for i in sorted(d.values()):
			m -= i
			if m < 0:
				return c
			else:
				c -= 1
		return c


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		hm = dict(Counter(arr))
		v = []
		for i in hm:
			v.append([hm[i], i])
		v.sort()
		c = 0
		for i in range(len(v)):
			if v[i][0] <= m:
				m -= v[i][0]
				c += 1
			else:
				return len(v) - c
		return len(v) - c


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		lis = []
		dic = {}
		count = 0
		s = 0
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for i in dic:
			lis.append(dic[i])
		lis.sort()
		for i in lis:
			count += 1
			s += i
			if m == s:
				break
			elif m < s:
				count -= 1
				break
		le = len(dic)
		return le - count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		count = {}
		for i in range(n):
			if arr[i] in count:
				count[arr[i]] += 1
			else:
				count[arr[i]] = 1
		count = sorted(count.items(), key=lambda x: x[1], reverse=True)
		while count and count[-1][1] <= m:
			m -= count.pop()[1]
		return len(count)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		mp = {}
		for num in arr:
			mp[num] = mp.get(num, 0) + 1
		arr = []
		for (k, v) in mp.items():
			arr.append([k, v])
		arr.sort(key=lambda x: x[1])
		for i in range(m):
			if len(arr) > 0:
				arr[0][1] = arr[0][1] - 1
				if arr[0][1] == 0:
					arr.pop(0)
		return len(arr)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		lst = []
		dic = {}
		k = m
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for i in dic.values():
			lst.append(i)
		lst.sort()
		sum = 0
		count = 0
		for i in lst:
			if sum + i <= k:
				sum += i
				count += 1
			else:
				break
		return len(lst) - count


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		x = Counter(arr)
		y = []
		for i in x.keys():
			y.append([x[i], i])
		y.sort()
		p = 0
		t = 0
		for i in range(len(y)):
			t += y[i][0]
			if t <= m:
				p += 1
		return len(y) - p


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		freq = {}
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = 1
			else:
				freq[arr[i]] += 1
		it = list(freq.items())
		it.sort(key=lambda x: x[1])
		c = 0
		for i in range(len(it)):
			if it[i][1] <= m:
				c += 1
				m -= it[i][1]
			else:
				break
		return len(it) - c


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		if m >= n:
			return 0
		c = Counter(arr)
		while c.most_common()[-1][1] <= m:
			m -= c.most_common()[-1][1]
			del c[c.most_common()[-1][0]]
		return len(c.keys())


import collections

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		if not arr:
			return 0
		sorted_count = sorted(collections.Counter(arr).items(), key=lambda x: x[1])
		while m > 0 and sorted_count:
			if sorted_count[0][1] <= m:
				m -= sorted_count[0][1]
				sorted_count.pop(0)
			else:
				break
		return len(sorted_count)


from collections import Counter

class Solution:

	def distinctIds(self, nums: list, n: int, k: int):
		freqCounter = Counter(nums)
		valList = list(freqCounter.values())
		valList.sort()
		for i in range(len(valList)):
			while valList[i] != 0 and k:
				valList[i] = valList[i] - 1
				k = k - 1
		id = 0
		for i in range(len(valList)):
			if valList[i] == 0:
				continue
			id += 1
		return id


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		di = dict()
		for i in arr:
			di[i] = di.get(i, 0) + 1
		n = len(di)
		arr = sorted(di.values())
		for i in arr:
			if m < i:
				break
			m -= i
			n -= 1
		return n


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		freq = {}
		for id in arr:
			if id in freq:
				freq[id] += 1
			else:
				freq[id] = 1
		freq = list(freq.values())
		freq.sort()
		n = len(freq)
		for i in freq:
			if m >= i:
				m -= i
				n -= 1
			else:
				break
		return n


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		freq = {}
		for id in arr:
			if id in freq:
				freq[id] += 1
			else:
				freq[id] = 1
		freq_val = list(freq.values())
		while m > 0 and len(freq_val) > 0:
			min_freq = min(freq_val)
			if m >= min_freq:
				m -= min_freq
				freq_val.remove(min_freq)
			else:
				break
		return len(freq_val)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		so = sorted(d.values())
		for i in range(min(m, len(so))):
			if m <= 0:
				break
			elif so[i] >= m:
				so[i] -= m
				m = 0
			else:
				m -= so[i]
				so[i] = 0
		return len(so) - so.count(0)


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		if m > len(arr):
			return 0
		mp = defaultdict(int)
		for i in range(n):
			mp[arr[i]] += 1
		k = list(mp.keys())
		k.sort(key=lambda i: mp[i])
		temp = 0
		i = 0
		while temp < m:
			if temp + mp[k[i]] <= m:
				temp += mp[k[i]]
				i += 1
			else:
				break
		return len(k) - i


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		a = Counter(arr)
		c = 0
		d = list(zip(a.values(), a.keys()))
		d.sort()
		size = len(d)
		for i in range(size):
			if d[i][0] <= m:
				m = m - d[i][0]
				c += 1
			else:
				return size - c
		return size - c


class Solution:

	def distinctIds(self, arr: list, n: int, mi: int):
		m = {}
		v = []
		c = 0
		for i in range(n):
			if arr[i] in m:
				m[arr[i]] += 1
			else:
				m[arr[i]] = 1
		for i in m:
			v.append([m[i], i])
		v.sort()
		size = len(v)
		for i in range(size):
			if v[i][0] <= mi:
				mi -= v[i][0]
				c += 1
			else:
				return size - c
		return size - c


import numpy as np

class Solution:

	def distinctIds(self, arr: list, n: int, mi: int):
		m = {}
		v = []
		count = 0
		for i in range(n):
			if arr[i] in m:
				m[arr[i]] += 1
			else:
				m[arr[i]] = 1
		for i in m:
			v.append([m[i], i])
		v.sort()
		size = len(v)
		for i in range(size):
			if v[i][0] <= mi:
				mi -= v[i][0]
				count += 1
			else:
				return size - count
		return size - count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		memo = {}
		for i in range(len(arr)):
			if arr[i] in memo:
				memo[arr[i]] += 1
			else:
				memo[arr[i]] = 1
		vector = []
		for i in memo:
			vector.append([memo[i], i])
		vector.sort()
		count = 0
		for i in range(len(vector)):
			if vector[i][0] <= m:
				m -= vector[i][0]
				count += 1
			else:
				break
		return len(vector) - count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		hashMap = {}
		for num in arr:
			if num not in hashMap:
				hashMap[num] = 1
			else:
				hashMap[num] += 1
		mapList = []
		for i in hashMap:
			mapList.append([hashMap[i], i])
		mapList.sort()
		removed = 0
		size = len(mapList)
		for i in range(size):
			if mapList[i][0] <= m:
				m -= mapList[i][0]
				removed += 1
			else:
				return size - removed
		return size - removed


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dic = Counter(arr)
		vals = sorted(dic, key=lambda x: dic[x])
		delete = 0
		i = 0
		if m >= n:
			return 0
		while delete < m:
			if dic[vals[i]] <= m - delete:
				delete += dic[vals[i]]
				del dic[vals[i]]
				i += 1
			else:
				break
		return len(dic.keys())


class Solution:

	def distinctIds(self, arr: list, n: int, p: int):
		m = {}
		for i in arr:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		b = []
		for i in m:
			b.append(m[i])
		b.sort()
		k = len(b)
		s = 0
		c = 0
		for i in b:
			s += i
			if s <= p:
				c += 1
			else:
				break
		return k - c


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		l = list(zip(d.values(), d.keys()))
		l.sort()
		c = 0
		k = len(l)
		for i in l:
			if i[0] <= m:
				m -= i[0]
				c += 1
			else:
				return k - c
		return k - c


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		x = []
		for i in d:
			x.append(d[i])
		x.sort(reverse=True)
		count = 0
		while m > 0 and len(x) > 0:
			if x[-1] <= m:
				m -= x[-1]
				count += 1
				x.pop()
			else:
				break
		return len(set(arr)) - count


from heapq import *
from collections import *

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		minheap = []
		heapify(minheap)
		freq = Counter(arr)
		for (ele, count) in freq.items():
			heappush(minheap, (count, ele))
		ucount = len(freq)
		while m and minheap:
			(count, ele) = heappop(minheap)
			if count - m <= 0:
				ucount -= 1
				m -= count
			else:
				break
		return ucount


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		temp = list(dic.values())
		temp.sort()
		ans = 0
		for i in range(len(temp)):
			if temp[i] <= m:
				m -= temp[i]
				ans += 1
			else:
				break
		return len(temp) - ans


def codeforces(arr, x):
	dst = {}
	for i in arr:
		try:
			dst[i] += 1
		except:
			dst[i] = 1
	res = []
	for i in dst:
		res.append(dst[i])
	res.sort(reverse=1)
	while x and res:
		top = res.pop()
		if x >= top:
			x -= top
		else:
			return len(res) + 1
	return len(res)

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		return codeforces(arr, m)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		x = {}
		for i in arr:
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
		y = []
		for i in x.keys():
			y.append([x[i], i])
		y.sort()
		p = 0
		t = 0
		for i in range(len(y)):
			t += y[i][0]
			if t <= m:
				p += 1
		return len(y) - p


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		di = Counter(arr)
		di = sorted(di.items(), key=lambda item: item[1])
		k = len(di)
		removed = 0
		for i in range(k):
			if di[i][1] <= m:
				m -= di[i][1]
				removed += 1
		return k - removed


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		from collections import Counter
		x = Counter(arr)
		y = []
		for i in x.keys():
			y.append([x[i], i])
		y.sort()
		p = 0
		t = 0
		for i in range(len(y)):
			t += y[i][0]
			if t <= m:
				p += 1
		return len(y) - p
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		m = int(input())
		ob = Solution()
		print(ob.distinctIds(arr, n, m))


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		arr_s = set(arr)
		dic = {}
		for i in range(len(arr)):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		v = []
		for i in dic:
			v.append([dic[i], i])
		v.sort()
		size = len(v)
		count = 0
		for i in range(size):
			if v[i][0] <= m:
				m -= v[i][0]
				count += 1
			else:
				return size - count
		return size - count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		m = int(input())
		ob = Solution()
		print(ob.distinctIds(arr, n, m))


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		dist = 0
		for i in arr:
			if i in d:
				d[i] += 1
			if i not in d:
				d[i] = 1
				dist += 1
		k = sorted(d, key=lambda x: d[x])
		l = 0
		flag = 0
		removed = 0
		for i in k:
			if flag == 1:
				break
			for _ in range(d[i]):
				if m <= 0:
					flag = 1
					break
				m -= 1
			if flag == 1:
				break
			removed += 1
		return dist - removed


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		hm = defaultdict(int)
		for i in arr:
			hm[i] += 1
		t = []
		for i in hm:
			t.append((i, hm[i]))
		t.sort(key=lambda x: x[1])
		k = 0
		for i in t:
			if i[1] <= m:
				m -= i[1]
				k += 1
			else:
				return len(t) - k
		return len(t) - k


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		if m > n:
			return 0
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		l = sorted(d.items(), key=lambda x: x[1])
		while m:
			if l[0][1] <= m:
				m -= l[0][1]
				l.pop(0)
			else:
				m = 0
		return len(l)


from collections import Counter
from heapq import heapify, heappush, heappop

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		heap = []
		d = Counter(arr)
		for (i, j) in d.items():
			heap.append([j, i])
		heapify(heap)
		while m > 0 and heap:
			(x, y) = heappop(heap)
			x -= 1
			if x != 0:
				heappush(heap, [x, y])
			m -= 1
		return len(heap)


class Solution:

	def distinctIds(self, a: list, n: int, m: int):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		a = sorted(d.items(), key=lambda x: x[1])
		ans = len(a)
		i = 0
		while i < len(a):
			val = a[i]
			if m and val[1] <= m:
				m -= val[1]
			else:
				break
			ans -= 1
			i += 1
		return ans


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		f = defaultdict(lambda : 0)
		for i in arr:
			f[i] += 1
		a = []
		for i in f:
			a.append((f[i], i))
		a.sort()
		while len(a) > 0:
			if m < a[0][0]:
				break
			m = m - a.pop(0)[0]
		return len(a)


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		c = Counter(arr)
		d = c.most_common()
		e = []
		for (i, j) in d:
			e += [i] * j
		k = len(e) - m if len(e) >= m else 0
		return len(set(e[:k]))


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		mymap = {}
		for ele in arr:
			mymap[ele] = 0
		for ele in arr:
			mymap[ele] = mymap[ele] + 1
		list1 = []
		for (key, value) in mymap.items():
			list1.append(value)
		mymap = list1
		mymap.sort()
		ans = len(mymap)
		for i in range(len(mymap)):
			if m <= 0:
				break
			while mymap[i] != 0 and m > 0:
				mymap[i] = mymap[i] - 1
				m = m - 1
		for i in range(len(mymap)):
			if mymap[i] == 0:
				ans = ans - 1
		return ans


import collections
import operator

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		count = collections.Counter(arr)
		res = []
		for i in count:
			res.append((count[i], i))
		res.sort()
		ans = 0
		l = len(res)
		for i in range(len(res)):
			if res[i][0] <= m:
				m -= res[i][0]
				ans += 1
			else:
				return l - ans
		return l - ans


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		l = []
		dict = {}
		count = 0
		for i in range(n):
			if arr[i] not in dict:
				count += 1
				dict[arr[i]] = 1
			else:
				dict[arr[i]] += 1
		for i in dict:
			l.append(dict[i])
		l.sort()
		for i in l:
			if i <= m:
				m = m - i
				count -= 1
			else:
				break
		return count


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		hm = {}
		y = []
		for i in arr:
			if i in hm:
				hm[i] += 1
			else:
				hm[i] = 1
		for (k, v) in hm.items():
			y.append([v, k])
		y.sort()
		r = 0
		t = 0
		for i in range(len(y)):
			t += y[i][0]
			if t <= m:
				r += 1
		return len(y) - r


from collections import deque

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dctn = {}
		arr.sort()
		count = 0
		for i in range(n):
			if arr[i] in dctn:
				dctn[arr[i]] += 1
			else:
				dctn[arr[i]] = 1
		temp = []
		for (key, value) in dctn.items():
			temp.append((key, value))
		dctn = temp
		dctn.sort(key=lambda x: x[1])
		dctn = deque(dctn)
		count = 0
		while dctn:
			elem = dctn.popleft()
			if m > 0:
				if elem[1] <= m:
					m -= elem[1]
					continue
				else:
					m = 0
					count += 1
			else:
				count += 1
		return count


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		cnt = Counter(arr)
		res = []
		for i in cnt.keys():
			res.append([cnt[i], i])
		res.sort()
		(l, r) = (0, 0)
		for i in range(len(res)):
			r += res[i][0]
			if r <= m:
				l += 1
		return len(res) - l


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		ids = {}
		for i in arr:
			if i in ids:
				ids[i] += 1
			else:
				ids[i] = 1
		ids_copy = ids.copy()
		for k in sorted(ids, key=ids.get, reverse=False):
			if ids[k] >= m:
				if ids[k] == m:
					ids_copy.pop(k, None)
				break
			else:
				m -= ids[k]
				ids_copy.pop(k, None)
		return len(ids_copy.keys())


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dic = {}
		for i in arr:
			try:
				dic[i] += 1
			except:
				dic[i] = 1
		l = list(dic.keys())
		l.sort(key=lambda x: dic[x])
		for i in l:
			if m >= dic[i]:
				m -= dic[i]
			else:
				return len(l) - l.index(i)
		return 0


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = Counter(arr)
		while m != 0:
			for i in d:
				k = min(d.values())
				if d[i] == k:
					d[i] = k - 1
					if d[i] == 0:
						d.pop(i)
					break
			m -= 1
		return len(d)


from collections import defaultdict

def distinct(arr, l):
	S = set()
	for i in range(l):
		S.add(arr[i])
	ans = len(S)
	return ans

def sortByFreq(arr, n):
	d = defaultdict(lambda : 0)
	for i in range(n):
		d[arr[i]] += 1
	arr.sort(key=lambda x: (d[x], x))
	return arr

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		arr = sortByFreq(arr, n)
		for i in range(m):
			if len(arr) == 0:
				break
			arr.pop(0)
		return distinct(arr, len(arr))


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		l = list(sorted(d.values()))
		leni = len(l)
		i = 0
		while i < leni:
			temp = m - l[i]
			if temp >= 0:
				m -= l[i]
				l.pop(i)
				leni -= 1
			else:
				break
		return len(l)


class Solution:

	def distinctIds(self, ids: list, n: int, m: int):
		hmap = {}
		for i in ids:
			if i not in hmap:
				hmap[i] = 1
			else:
				hmap[i] += 1
		x = sorted(hmap.items(), key=lambda kv: (kv[1], kv[0]))
		s = 0
		for i in x:
			if m > 0:
				m -= i[-1]
				s += 1
			elif m < 0:
				return len(x) - s + 1
			else:
				return len(x) - s
		if m < 0:
			return len(x) - s + 1
		else:
			return len(x) - s


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = 0
		d = sorted(d.items(), key=lambda x: x[1])
		for (k, v) in d:
			if v <= m:
				m -= v
				c += 1
			else:
				return len(d) - c
		return len(d) - c


from collections import defaultdict

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = defaultdict(lambda : 0)
		for i in arr:
			d[i] += 1
		r = 0
		i = 0
		d = sorted(list(d.values()))
		while r < m and i < len(d):
			r += d[i]
			i += 1
		if r > m:
			i -= 1
		i -= 1
		return len(d) - i - 1


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		key = sorted(d.keys(), key=lambda x: d[x])
		i = 0
		while d and m > 0:
			d[key[i]] -= 1
			if d[key[i]] == 0:
				del d[key[i]]
				i += 1
			m -= 1
		return len(d)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		w = {}
		minlen = 0
		for i in arr:
			if i not in w:
				w[i] = 1
				minlen += 1
			else:
				w[i] += 1
		k = list(w.items())
		k.sort(key=lambda x: x[1])
		for i in k:
			if m == 0 or m < i[1]:
				break
			else:
				minlen -= 1
				m -= i[1]
		return minlen


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for i in d:
			l.append([d[i], i])
		l.sort()
		t = p = 0
		for i in range(len(l)):
			t += l[i][0]
			if t <= m:
				p += 1
		return len(l) - p


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dict = {}
		for i in arr:
			if dict.get(i):
				dict[i] += 1
			else:
				dict[i] = 1
		sort_ele = sorted(dict, key=lambda i: dict[i])
		size = len(sort_ele)
		while m and size > 0:
			if dict[sort_ele[0]] <= m:
				m -= dict[sort_ele[0]]
				sort_ele.pop(0)
				size -= 1
			else:
				break
		return len(sort_ele)


class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		d = dict()
		for i in arr:
			d[i] = 0
		for i in arr:
			d[i] = d[i] + 1
		l = []
		for i in d.keys():
			l.append([d[i], i])
		l.sort()
		for i in l:
			if i[0] <= m:
				m = m - i[0]
				i[0] = 0
				continue
			if i[0] > m:
				break
		count = 0
		for i in l:
			if i[0] != 0:
				count = count + 1
		return count


from collections import Counter

class Solution:

	def distinctIds(self, arr: list, n: int, m: int):
		dic = Counter(arr)
		ls = sorted([dic[i] for i in dic])
		for i in range(len(ls)):
			if ls[i] > m:
				ls[i] -= m
				m = 0
			else:
				m -= ls[i]
				ls[i] = 0
			if not m:
				return len([i for i in ls if i])
		else:
			return 0