Given an array arr of size N, the goal is to find out the smallest number that is repeated exactly ‘K’ times.
 
Example 1:
Input:
N=5, K=2
arr[] = { 2 2 1 3 1 }
Output: 1
Explanation: Here in array,
2 is repeated 2 times, 1 is repeated
2 times, 3 is repeated 1 time.
Hence 2 and 1 both are repeated 'k' 
times i.e 2 and min(2, 1) is 1 .
 
Example 2:
Input:
N=4, K=1 
arr[] = { 3 5 3 2 }
Output:  2 
Explanation: Both 2 and 5 are repeating 1
time but min(5, 2) is 2.
 
Your Task:
You just need to complete the function findDuplicate() that takes array arr, integer N and integer K as parameters and returns the required answer.
Note- If there is no such element then return -1.
 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(MAX). where MAX is maximum element in the array.
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3


class Solution:
    def findDuplicate(self, arr, N, K):


Solutions:
class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		a = {}
		for i in range(N):
			if arr[i] not in a:
				a[arr[i]] = 1
			else:
				a[arr[i]] += 1
		for i in a:
			if a[i] == K:
				return i
				break


class Solution:

	def findDuplicate(self, arr, N, k):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		mc = 99999
		for i in d:
			if d[i] == k and i < mc:
				mc = i
		return mc


class Solution:

	def findDuplicate(self, arr, N, K):
		dict = []
		for x in arr:
			if arr.count(x) == K:
				dict.append(x)
		min = dict[0]
		for x in range(len(dict) - 1):
			if min > dict[x + 1]:
				min = dict[x + 1]
		return min


class Solution:

	def findDuplicate(self, arr, N, K):
		dict = []
		for x in arr:
			if arr.count(x) == K:
				dict.append(x)
		return min(dict)


class Solution:

	def findDuplicate(self, arr, N, K):
		l = []
		a = set(arr)
		for i in a:
			if arr.count(i) == K:
				l = l + [i]
		if len(l):
			return min(l)
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		m = min(arr)
		if arr.count(m) == K:
			return m
		else:
			l = []
			for i in arr:
				if arr.count(i) == K:
					l.append(i)
			return min(l)


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		a = Counter(arr)
		b = list(a.keys())
		c = list(a.values())
		d = []
		for i in range(N):
			if c[i] == K:
				d.append(b[i])
				return min(d)


class Solution:

	def findDuplicate(self, arr, N, K):
		di = {}
		for i in arr:
			di[i] = di.get(i, 0) + 1
		di = sorted(di.items(), key=lambda x: (x[1], x[0]))
		for i in range(N):
			if di[i][1] == K:
				return di[i][0]
		return -1


class Solution:

	def findDuplicate(self, arr, N, k):
		l = []
		for i in arr:
			if arr.count(i) == k:
				l.append(i)
		return min(l)


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		c = Counter(arr)
		res = [key for (key, val) in c.items() if val == K]
		return min(res)


class Solution:

	def findDuplicate(self, arr, N, K):
		table = {}
		for i in arr:
			if i in table:
				table[i] += 1
			else:
				table[i] = 1
		mini = 10 ** 9
		flag = False
		for j in table:
			if table[j] == K:
				flag = True
				if j < mini:
					mini = j
		if flag:
			return mini
		else:
			return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		d = dict()
		a = []
		for ele in arr:
			d[ele] = 0
		for ele in arr:
			d[ele] = d[ele] + 1
		for (k, v) in d.items():
			if v == K:
				a.append(k)
		return min(a)


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		for i in arr:
			if dic[i] == K:
				return i
		return -1


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		d = Counter(arr)
		ans = 10 ** 9 + 7
		if K not in d.values():
			return -1
		else:
			for (i, j) in d.items():
				if j == K:
					ans = min(ans, i)
		return ans


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		for i in arr:
			if arr.count(i) == K:
				return i


class Solution:

	def findDuplicate(self, arr, N, K):
		from collections import Counter
		arr = Counter(arr)
		c = []
		for i in arr:
			if arr[i] == K:
				c.append(i)
		return min(c)


class Solution:

	def findDuplicate(self, arr, N, K):
		out = -1
		d = {}
		l = []
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if d[i] == K:
				l.append(i)
		out = min(l)
		return out


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		a = Counter(arr)
		for i in range(N):
			if a[arr[i]] == K:
				return arr[i]


class Solution:

	def findDuplicate(self, arr, N, K):
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 1
			else:
				freq[i] += 1
		mi = 100000000.0
		for i in freq:
			if freq[i] == K:
				mi = min(mi, i)
		if mi == 100000000.0:
			return -1
		return mi


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		l = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (i, j) in d.items():
			if j == K:
				l.append(i)
		sorted(l)
		return l[0]


class Solution:

	def findDuplicate(self, arr, N, K):
		dict_ = {}
		e = []
		for elem in arr:
			dict_.update({elem: dict_.get(elem, 0) + 1})
		return list(dict_.keys())[list(dict_.values()).index(K)]


from collections import *

class Solution:

	def findDuplicate(self, arr, N, K):
		new_arr = Counter(arr)
		res = [key for (key, value) in new_arr.items() if value == K]
		return min(res)


class Solution:

	def findDuplicate(self, arr, N, K):
		s = {}
		for i in arr:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		ans = []
		for i in s:
			if s[i] == K:
				ans.append(i)
		return min(ans)


class Solution:

	def findDuplicate(self, arr, N, K):
		dp = {}
		for i in arr:
			if i in dp:
				dp[i] += 1
			else:
				dp[i] = 1
		maxi = 1000000
		for (key, value) in dp.items():
			if value == K:
				if key < maxi:
					maxi = key
		return maxi


class Solution:

	def findDuplicate(self, arr, n, k):
		d = dict()
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		ans = []
		for (key, value) in d.items():
			if value == k:
				ans.append(key)
		return min(ans)


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		count = 1
		for i in range(N - 1):
			if arr[i] == arr[i + 1]:
				count += 1
			elif count == K:
				return arr[i]
			else:
				count = 1
		return arr[N - 1]


class Solution:

	def findDuplicate(self, a, N, k):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		ans = pow(10, 7)
		for i in d:
			if d[i] == k:
				ans = min(i, ans)
		if ans == pow(10, 7):
			return -1
		return ans


class Solution:

	def findDuplicate(self, arr, N, K):
		for number in set(arr):
			if arr.count(number) == K:
				return number
				break
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		li = []
		for i in range(N):
			if arr.count(arr[i]) == K:
				li.append(arr[i])
		return min(li)


class Solution:

	def findDuplicate(self, arr, N, K):
		m = max(arr)
		for i in set(arr):
			if arr.count(i) == K:
				m = min(m, i)
		return m


from collections import defaultdict

class Solution:

	def findDuplicate(self, arr, N, K):
		res = []
		def_d = defaultdict()
		for i in arr:
			if i in def_d:
				def_d[i] += 1
			else:
				def_d[i] = 1
		for i in arr:
			if def_d[i] == K:
				res.append(i)
		return min(res)


class Solution:

	def findDuplicate(self, arr, N, K):
		c = {}
		for i in arr:
			if i in c:
				c[i] += 1
			else:
				c[i] = 1
		if len(c.keys()) > 0:
			for i in c.keys():
				if c[i] == K:
					return i
				pass
		else:
			return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in range(N):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		res = []
		for (key, value) in d.items():
			if value == K:
				res.append(key)
		return min(res)


class Solution:

	def findDuplicate(self, arr, N, K):
		freq = {}
		for i in arr:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		res = []
		for (e, v) in freq.items():
			if v == K:
				res.append(e)
		return min(res)


class Solution:

	def findDuplicate(self, arr, N, j):
		d = {}
		a = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (k, v) in d.items():
			if v == j:
				a.append(k)
		return min(a)


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		k = -1
		for i in range(N):
			if arr.count(arr[i]) == K:
				k = arr[i]
				break
		return k


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in range(len(arr)):
			if d.get(arr[i], -1) == -1:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		ans = 9765435432345543
		for key in d:
			if d[key] == K:
				ans = min(ans, key)
		return ans


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		a = Counter(arr)
		l = []
		for i in a.keys():
			if a[i] == K:
				l.append(i)
		return min(l)


class Solution:

	def findDuplicate(self, arr, N, K):
		lst = [0] * (max(arr) + 1)
		for i in arr:
			lst[i] += 1
		for i in range(max(arr) + 1):
			if lst[i] == K:
				return i
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		Hash = {}
		arr.sort()
		for i in arr:
			if i in Hash:
				Hash[i] += 1
			else:
				Hash[i] = 1
		for i in Hash:
			if Hash[i] == K:
				return i
		return -1


class Solution:

	def findDuplicate(self, arr, n, k):
		mx = max(arr)
		mn = min(arr)
		count = [0] * (mx - mn + 1)
		for num in arr:
			count[num - mn] += 1
		for i in range(len(count)):
			if count[i] == k:
				return i + mn
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		numbers = {}
		for element in arr:
			numbers[element] = numbers.get(element, 0) + 1
		for key in numbers.keys():
			if numbers[key] == K:
				return key
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		minkey = float('inf')
		H = {}
		for i in range(N):
			H[arr[i]] = H.get(arr[i], 0) + 1
		for key in H.keys():
			if H[key] == K:
				minkey = min(minkey, key)
		return minkey


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		temp_arr = Counter(arr)
		temp_list = [key for (key, value) in temp_arr.items() if value == K]
		return min(temp_list)


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for j in arr:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
		m = 10 ** 5 + 1
		for i in d:
			if d[i] == K:
				if i < m:
					m = i
		return m


class Solution:

	def findDuplicate(self, arr, N, K):
		b = list(set(arr))
		for i in range(len(b)):
			if arr.count(b[i]) == K:
				return b[i]
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] = dic[i] + 1
			if i not in dic:
				dic[i] = 1
		maxi = 1000000
		for (key, value) in dic.items():
			if value == K:
				maxi = min(maxi, key)
		return maxi


class Solution:

	def findDuplicate(self, arr, N, K):
		s = set(arr)
		for i in s:
			if arr.count(i) == K:
				return i


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		c = Counter(arr)
		for item in c:
			if c[item] == K:
				return item
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		curr = []
		for i in arr:
			if i not in curr:
				curr.append(i)
		curr.sort()
		lst = []
		for i in curr:
			lst.append(arr.count(i))
		for j in range(len(lst)):
			if K == lst[j]:
				return curr[j]
				break


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		a = []
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		for (i, j) in d.items():
			if j == K:
				a.append(i)
		m = min(a)
		return m


from collections import Counter

class Solution:

	def findDuplicate(self, arr, N, K):
		m = Counter(arr)
		l = []
		for (keys, values) in m.items():
			if values == K:
				l.append(keys)
		return min(l)


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		for x in arr:
			if arr.count(x) == K:
				return x
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		ans = set()
		for v in arr:
			if arr.count(v) == K:
				ans.add(v)
		return min(ans)


class Solution:

	def findDuplicate(self, arr, N, K):
		ans = []
		for v in arr:
			if arr.count(v) == K:
				ans.append(v)
		return min(ans)


class Solution:

	def findDuplicate(self, arr, n, k):
		s = set(arr)
		ar = []
		for i in s:
			if arr.count(i) == k:
				ar.append(i)
		return min(ar)


class Solution:

	def findDuplicate(self, arr, N, K):
		s = set(arr)
		l = []
		for i in s:
			if arr.count(i) == K:
				l.append(i)
		sorted(l)
		return l[0]


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		ans = 0
		m = 1000000000000000
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (i, j) in zip(d.values(), d.keys()):
			if i == K and j < m:
				m = j
		return m


class Solution:

	def findDuplicate(self, arr, N, K):
		a = []
		for i in arr:
			if arr.count(i) == K:
				a.append(i)
		a.sort()
		return a[0]


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		d = dict()
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for (k, v) in d.items():
			if v == K:
				return k


class Solution:

	def findDuplicate(self, arr, N, K):
		count = []
		for i in arr:
			if a.count(i) == K:
				count.append(i)
		return min(count)


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in range(N):
			if arr[i] in d:
				d[arr[i]] = d[arr[i]] + 1
			else:
				d[arr[i]] = 1
		mn = 10000000
		for i in d:
			if d[i] == K:
				mn = min(mn, i)
		return mn


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in range(N):
			if arr[i] in d.keys():
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		for i in sorted(d):
			if d[i] == K:
				return i


class Solution:

	def findDuplicate(self, arr, N, K):
		x = []
		for i in set(arr):
			if arr.count(i) == K:
				x.append(i)
		return min(x)


class Solution:

	def findDuplicate(self, arr, N, K):
		h = {}
		for i in arr:
			h[i] = 1 + h.get(i, 0)
		mini = 99999
		for i in h:
			if h[i] == K and i < mini:
				mini = i
		if mini == 99999:
			return -1
		return mini


class Solution:

	def findDuplicate(self, arr, N, K):
		arr.sort()
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (key, val) in d.items():
			if val == K:
				return key


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (k1, v1) in d.items():
			if v1 == K:
				return k1
		return -1


class Solution:

	def findDuplicate(self, arr, N, K):
		counter = {}
		for i in range(N):
			if arr[i] in counter:
				counter[arr[i]] += 1
			else:
				counter[arr[i]] = 1
		counter = {key: v for (key, v) in counter.items() if v == K}
		if not counter:
			return -1
		else:
			return min(counter)


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		small = 10000000
		for (key, value) in d.items():
			if value == K and small > key:
				small = key
		if small == 10000000:
			return -1
		return small


class Solution:

	def findDuplicate(self, arr, N, k):
		d = dict()
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		v = []
		for i in d:
			if d[i] == k:
				v.append(i)
		if len(v) == 0:
			return -1
		return min(v)


class Solution:

	def findDuplicate(self, arr, N, K):
		d = {}
		l = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] == K:
				l.append(i)
		l.sort()
		return l[0]


class Solution:

	def findDuplicate(self, arr, N, k):
		mydict = {}
		for i in arr:
			mydict[i] = mydict.get(i, 0) + 1
		res = float('inf')
		for (key, value) in mydict.items():
			if value == k:
				res = min(res, key)
		return res if res != float('inf') else -1


class Solution:

	def findDuplicate(self, arr, N, K):
		mapp = {}
		minVal = 9999999
		for i in range(N):
			if arr[i] not in mapp.keys():
				mapp[arr[i]] = 1
			else:
				mapp[arr[i]] += 1
		if len(mapp.keys()) > 0:
			for key in mapp.keys():
				if mapp[key] == K:
					minVal = min(minVal, key)
		if minVal == 9999999:
			return -1
		return minVal