Given an array of integers the task is to find maximum size of a subset such that sum of each pair of this subset is not divisible by K.
 
Example 1:
Input : 
arr[] = [3, 7, 2, 9, 1]       
K = 3
Output : 
3
Explanation:
Maximum size subset whose each pair sum
is not divisible by K is [3, 7, 1] because,
3+7 = 10,   
3+1 = 4,   
7+1 = 8 
These all are not divisible by 3.
It is not possible to get a subset of size
bigger than 3 with the above-mentioned property.
 
Example 2:
Input :
arr[] = [3, 17, 12, 9, 11, 15]
K = 5
Output :
4 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function subsetPairNotDivisibleByK() which takes the array A[], its size N and an integer K as inputs and returns the required answer.
 
Expected Time Complexity: O(N+K)
Expected Auxiliary Space: O(K)
 
Constraints:
1<= N, K <=10^{5}
1<= Arr[] <=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Data structures

Starter code: 



def subsetPairNotDivisibleByK( a, N, K):
    
    
    


Solutions:
def subsetPairNotDivisibleByK(arr, N, K):
	f = [0 for i in range(K)]
	for i in range(N):
		f[arr[i] % K] += 1
	if K % 2 == 0:
		f[K // 2] = min(f[K // 2], 1)
	res = min(f[0], 1)
	for i in range(1, K // 2 + 1):
		res += max(f[i], f[K - i])
	return res


from collections import defaultdict

def subsetPairNotDivisibleByK(arr, n, k):
	d = defaultdict(int)
	ans = 0
	for i in arr:
		if d[i % k]:
			d[i % k] += 1
		else:
			d[i % k] = 1
	if k % 2 == 0:
		d[k // 2] = min(d[k // 2], 1)
	ans = min(d[0], 1)
	for i in range(1, k // 2 + 1):
		ans += max(d[i], d[k - i])
	return ans


def subsetPairNotDivisibleByK(a, N, K):
	freq = [0] * K
	for i in range(N):
		pos = a[i] % K
		freq[pos] += 1
	if K % 2 == 0:
		freq[K // 2] = min(freq[K // 2], 1)
	res = min(freq[0], 1)
	for i in range(1, K // 2 + 1):
		res += max(freq[i], freq[K - i])
	return res


def subsetPairNotDivisibleByK(a, N, K):
	if K == 1:
		return 1
	remainders = {}
	for item in a:
		rem = item % K
		remainders[rem] = remainders.get(rem, 0) + 1
	count = 1 if 0 in remainders else 0
	for remainder in range(1, K // 2 + 1):
		if remainder == K / 2:
			count += 1 if remainder in remainders else 0
			break
		count += max(remainders.get(remainder, 0), remainders.get(K - remainder, 0))
	return count


def subsetPairNotDivisibleByK(arr, N, K):
	freq = [0] * K
	for i in arr:
		rem = i % K
		freq[rem] = freq[rem] + 1
	max_size = 0
	for rem in range(K // 2 + 1):
		if rem == 0:
			max_size = max_size + min(1, freq[rem])
		elif K % 2 == 0 and rem == K // 2:
			max_size = max_size + min(1, freq[K // 2])
		else:
			max_size = max_size + max(freq[rem], freq[K - rem])
	return max_size

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, k) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(subsetPairNotDivisibleByK(a, n, k))
		T -= 1
if __name__ == '__main__':
	main()


def subsetPairNotDivisibleByK(a, N, K):
	k = K
	rq = {}
	rslt = set()
	for i in a:
		r = i % k
		if r in rq.keys():
			rq[r].append(i)
		else:
			rq[r] = [i]
	sel = set([0, k / 2])
	rslt = 0
	for i in rq.keys():
		if i not in sel:
			if abs(k - i) in rq.keys():
				sel.add(abs(k - i))
				if len(rq[i]) >= len(rq[abs(k - i)]):
					rslt = rslt + len(rq[i])
				else:
					rslt = rslt + len(rq[abs(k - i)])
			else:
				rslt = rslt + len(rq[i])
	if 0 in rq.keys():
		rslt = rslt + 1
	if k / 2 in rq.keys():
		rslt = rslt + 1
	return rslt

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, k) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(subsetPairNotDivisibleByK(a, n, k))
		T -= 1
if __name__ == '__main__':
	main()


def subsetPairNotDivisibleByK(a, N, k):
	count = [0] * k
	for i in a:
		remainder = i % k
		count[remainder] += 1
	ans = min(count[0], 1)
	if k % 2 == 0:
		ans += min(count[k // 2], 1)
	for i in range(1, k // 2 + 1):
		if i != k - i:
			ans += max(count[i], count[k - i])
	return ans


def subsetPairNotDivisibleByK(a, N, K):
	div = [0] * K
	for i in a:
		c = (i % K + K) % K
		div[c] += 1
	su = 1 if div[0] != 0 else 0
	if K % 2 == 0:
		for i in range(1, K // 2):
			su += max(div[i], div[K - i])
		su = su + (1 if div[K // 2] != 0 else 0)
	else:
		for i in range(1, K // 2 + 1):
			su += max(div[i], div[K - i])
	return su


def subsetPairNotDivisibleByK(a, N, K):
	n = len(a)
	rf = [0] * K
	for v in a:
		rf[v % K] += 1
	if K % 2 == 0:
		rf[K // 2] = min(rf[K // 2], 1)
	rf[0] = min(rf[0], 1)
	ans = min(rf[0], 1)
	for i in range(1, K // 2 + 1):
		ans += max(rf[i], rf[K - i])
	return ans


import math

def max_nondivisable_subset(arr, k):
	b = [0] * k
	max_ = 0
	for i in range(0, len(arr)):
		b[arr[i] % k] += 1
	up_to = 0
	if k % 2 == 0:
		up_to = int(k / 2) + 1
	else:
		up_to = int(math.ceil(k / 2))
	for i in range(0, up_to):
		if i == 0:
			if b[i] > 0:
				max_ += 1
		elif i == k - i:
			if b[i] > 0:
				max_ += 1
		elif b[i] > b[k - i]:
			max_ += b[i]
		else:
			max_ += b[k - i]
	return max_

def subsetPairNotDivisibleByK(a, N, K):
	return max_nondivisable_subset(a, K)


from collections import defaultdict as d

def subsetPairNotDivisibleByK(a, N, K):
	dic = d(int)
	for i in a:
		dic[i % K] += 1
	ans = 0
	for i in range(1, (K + 1) // 2):
		ans += max(dic[i], dic[K - i])
	if dic[0] > 0:
		ans += 1
	if K & 1 == 0 and dic[K // 2] > 0:
		ans += 1
	return ans


def subsetPairNotDivisibleByK(a, N, K):
	size = 0
	li = [0 for i in range(K)]
	for i in range(N):
		li[a[i] % K] += 1
	res = min(li[0], 1)
	if K % 2 == 0:
		li[K // 2] = min(li[K // 2], 1)
	for i in range(1, K // 2 + 1):
		res += max(li[i], li[K - i])
	return res