There are N integers given in an array arr. You have to determine if it is possible to divide them in at most K groups, such that any group does not have a single integer more than twice.
Example 1:
Input: N = 5, K = 2
arr = {1, 1, 2, 5, 1}
Output: 1
Explaination: We can divide them in two groups in 
following way (1, 1, 2, 5) and (1).
Example 2:
Input: N = 3, K = 1
arr = {1, 1, 1}
Output: 0
Explaination: There can be only one group and 
three 1's. So it is not possible.
Your Task:
You do not need to read input or print anything. Your Task is to complete the function isPossible() which takes the value N, K and arr as input parameters and returns 1 if grouping is posible. Otherwise returns 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 1000
1 ≤ K ≤ 256
1 ≤ arr[i] ≤ 32

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def isPossible(self, N, arr, K):
        # code here

Solutions:
class Solution:

	def isPossible(self, N, arr, K):
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		m = 0
		for i in freq:
			m = max(m, freq[i])
		if m > 2 * K:
			return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] % 2 == 0:
				d[i] = d[i] // 2
			else:
				d[i] = d[i] // 2 + 1
		for i in d:
			if d[i] > K:
				return 0
		return 1


from collections import Counter

class Solution:

	def isPossible(self, N, arr, K):
		return 1 if K * 2 >= Counter(arr).most_common()[0][1] else 0


class Solution:

	def isPossible(self, N, arr, k):
		mapp = {}
		for ele in arr:
			mapp[ele] = mapp.get(ele, 0) + 1
		for ele in mapp:
			if mapp[ele] > 2 * k:
				return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		b = set(arr)
		f = 0
		for i in b:
			if arr.count(i) > 2 * K:
				f = 1
				break
			else:
				continue
		if f == 1:
			return 0
		else:
			return 1


class Solution:

	def isPossible(self, n, arr, k):
		b = set(arr)
		f = 0
		for i in b:
			if arr.count(i) > 2 * k:
				f = 1
				break
		if f == 1:
			return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		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] / K)
		if max(x) > 2:
			return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, N, arr, K):
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		for i in d:
			if d[i] > 2 * K:
				return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		K = int(input())
		ob = Solution()
		print(ob.isPossible(N, arr, K))


class Solution:

	def isPossible(self, N, arr, K):
		Dict_ = {}
		for i in range(N):
			if arr[i] not in Dict_:
				Dict_[arr[i]] = 1
			else:
				Dict_[arr[i]] += 1
		flag = 1
		for (key, val) in Dict_.items():
			if val > 2 * K:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, N, arr, K):
		arr = arr
		n = N
		k = K
		mp = defaultdict(lambda : 0)
		for i in range(n):
			mp[arr[i]] += 1
		for (key, values) in mp.items():
			if values > 2 * k:
				return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		d = {}
		for i in arr:
			try:
				if d[i]:
					d[i] += 1
			except:
				d[i] = 1
		for i in d.values():
			if i / K > 2:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, N, arr, K):
		d = defaultdict(lambda : 0)
		for i in arr:
			d[i] += 1
		for i in d:
			if d[i] > K * 2:
				return 0
		return 1


class Solution:

	def isPossible(self, n, a, K):
		d = {}
		for i in range(n):
			if a[i] not in d:
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		for key in d:
			if d[key] > 2 * K:
				return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for i in dic.values():
			if i > 2 * K:
				return 0
		return 1


class Solution:

	def isPossible(self, N, arr, K):
		d = {}
		for i in arr:
			if d.get(i, None) is None:
				d[i] = 1
			else:
				d[i] += 1
		for k in d:
			if d[k] > 2 * K:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, n, arr, k):
		dd = defaultdict(int)
		for num in arr:
			dd[num] += 1
		for val in dd.values():
			if val > k * 2:
				return 0
		return 1