One day Jim came across array arr[] of N numbers. He decided to divide these N numbers into different groups. Each group contains numbers in which sum of any two numbers should not be divisible by an integer K. Print the size of the group containing maximum numbers.There will be atleast one number which is not divisible by K.
 
Example 1:
Input:
N = 4, K = 8
arr[] = {1, 7, 2, 6}
Output:
2
Explanation:
The  group of numbers which can be formed
are: (1),(2),(7),(6),(1,2),(1,6),(7,2),(7,6).
So,the maximum possible size of the group is 2.
Example 2:
Input:
N = 2, K = 3
arr[] = {1, 2}
Output:
1
Explanation:
The  group of numbers which can be formed
are: (1),(2). So,the maximum possible size
of the group is 1.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxGroupSize() which takes 2 Integers N, and K and also an array arr[] of N integers as input and returns the maximum group size possible.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(K)
 
Constraints:
1 ≤ N,K,arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def maxGroupSize(self, arr, N, K):

        # code here 

Solutions:
class Solution:

	def maxGroupSize(self, arr, N, K):
		rem = [0] * K
		for num in arr:
			rem[num % K] += 1
		res = 0
		(l, r) = (1, K - 1)
		while l < r:
			res += max(rem[l], rem[r])
			l += 1
			r -= 1
		if l == r and rem[l] > 0:
			res += 1
		if rem[0] > 0:
			res += 1
		return res


class Solution:

	def maxGroupSize(self, arr, N, K):
		a = [0] * K
		for r in arr:
			a[r % K] += 1
		ans = 0
		for i in range(1, (K + 1) // 2):
			ans += max(a[i], a[K - i])
		if K & 1 == 0 and a[K // 2] != 0:
			ans += 1
		if a[0] != 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		from collections import Counter
		arr = [i % K for i in arr]
		ans = 0
		c = Counter(arr)
		for i in range(0, K // 2 + 1):
			if i == 0 or (K % 2 == 0 and i == K // 2):
				ans += min(1, c[i])
			else:
				ans += max(c[i], c[K - i])
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		rem = [0] * K
		for i in range(N):
			rem[arr[i] % K] += 1
		i = 1
		j = K - 1
		c = 0
		while i < j:
			c += max(rem[i], rem[j])
			i += 1
			j -= 1
		if i == j and rem[i] > 0:
			c += 1
		if rem[0] > 0:
			c += 1
		return c


class Solution:

	def maxGroupSize(self, arr, N, K):
		dic = {}
		for i in arr:
			num = i % K
			dic[num] = dic.get(num, 0) + 1
		already = {}
		count = 0
		for i in dic:
			if K - i == i or i == 0:
				count += 1
			elif K - i in already:
				count_first = already[K - i]
				count_second = dic[i]
				if count_second > count_first:
					count -= count_first
					count += count_second
					del already[K - i]
			else:
				already[i] = dic[i]
				count += dic[i]
		return count


class Solution:

	def maxGroupSize(self, arr, N, K):
		ns = [0] * K
		for e in arr:
			ns[e % K] += 1
		ans = ns[0] > 0
		for i in range(1, K // 2 + 1):
			if i * 2 == K:
				ans += ns[i] > 0
			else:
				ans += max(ns[i], ns[K - i])
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		a = [0] * K
		for l in arr:
			a[l % K] = a[l % K] + 1
		b = 0
		for i in range(1, (K + 1) // 2):
			b += max(a[i], a[K - i])
		if K & 1 == 0 and a[K // 2] != 0:
			b += 1
		if a[0] != 0:
			b += 1
		return b


class Solution:

	def maxGroupSize(self, arr, N, K):
		if N == 1:
			return 1
		a = [0] * K
		for i in range(N):
			a[arr[i] % K] += 1
		summ = 0
		if a[0] > 0:
			summ += 1
		for i in range(1, (K + 1) // 2):
			summ += max(a[i], a[K - i])
		if K % 2 == 0 and a[K // 2] > 0:
			summ += 1
			pass
		return summ


class Solution:

	def maxGroupSize(self, arr, N, K):
		from collections import defaultdict
		di = defaultdict(int)
		for i in arr:
			rem = i % K
			di[rem] += 1
		ans = 0
		low = 1
		high = K - 1
		while low < high:
			ans += max(di[low], di[high])
			low += 1
			high -= 1
		if low == high:
			ans += min(1, di[low])
		ans += min(1, di[0])
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		remainderFreq = [0] * K
		for val in arr:
			remainderFreq[val % K] += 1
		count = 0
		count = remainderFreq[0] != 0
		i = 1
		j = K - 1
		while i < j:
			count += max(remainderFreq[i], remainderFreq[j])
			i += 1
			j -= 1
		if i == j and remainderFreq[i]:
			count += 1
		return count


class Solution:

	def maxGroupSize(self, arr, N, K):
		if N == 1:
			return 1
		l = [0] * K
		for i in arr:
			l[i % K] += 1
		c = 0
		if l[0] > 0:
			c += 1
		d = (K + 1) // 2
		for i in range(1, d):
			c += max(l[i], l[K - i])
		if K % 2 == 0 and l[K // 2] > 0:
			c += 1
			pass
		return c


class Solution:

	def maxGroupSize(self, arr, n, k):
		dp = [0] * k
		for i in arr:
			dp[i % k] += 1
		res = 0
		if dp[0]:
			res += 1
		if not k & 1:
			if dp[k // 2]:
				res += 1
		for i in range(1, k - k // 2):
			res += max(dp[i], dp[k - i])
		return res


class Solution:

	def maxGroupSize(self, arr, N, K):
		dc = [0] * K
		for num in arr:
			dc[num % K] += 1
		ans = 0
		for i in range(1, (K + 1) // 2):
			ans += max(dc[i], dc[K - i])
		if dc[0]:
			ans += 1
		if K % 2 == 0 and dc[K // 2]:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		resturi = [0] * K
		for i in arr:
			resturi[i % K] += 1
		maxim = 0
		for i in range(1, (K + 1) // 2):
			maxim += max(resturi[i], resturi[K - i])
		if K % 2 == 0 and resturi[K // 2] > 0:
			maxim += 1
		if resturi[0] > 0:
			maxim += 1
		return maxim


class Solution:

	def maxGroupSize(self, arr, N, K):
		a = [0] * K
		k = K
		for i in range(N):
			a[arr[i] % K] += 1
		ans = 0
		for i in range(1, K // 2 + 1):
			if i != K - i:
				ans += max(a[i], a[K - i])
			elif a[i] != 0:
				ans += 1
		if a[0] != 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		pairs = {}
		for i in arr:
			i = i % K
			if i not in pairs:
				pairs[i] = 0
			pairs[i] += 1
		m = 0
		extra = 0
		for i in pairs:
			if i == 0:
				m += 1
			elif K - i == i:
				m += 1
			elif K - i in pairs:
				p = max(pairs[K - i], pairs[i])
				m += p
				extra += p
			else:
				m += pairs[i]
		m -= extra // 2
		return m


class Solution:

	def maxGroupSize(self, arr, N, K):
		res = [0] * K
		for i in arr:
			res[i % K] += 1
		ans = 0
		ans += 1 if res[0] else 0
		i = 1
		j = len(res) - 1
		while i < j:
			ans += max(res[i], res[j])
			i += 1
			j -= 1
		if i == j:
			ans += 1 if res[i] else 0
		return 1 if ans == 0 else ans


class Solution:

	def maxGroupSize(self, arr, N, k):
		remainders = [0] * k
		for e in arr:
			remainders[e % k] += 1
		sz = 0
		for i in range(1, k // 2 + 1):
			if i != k - i:
				sz += max(remainders[i], remainders[k - i])
			elif remainders[i] != 0:
				sz += 1
		if remainders[0] != 0:
			sz += 1
		return sz


class Solution:

	def maxGroupSize(self, arr, N, K):
		d = dict()
		for x in range(K + 1):
			d[x] = 0
		for x in arr:
			n = x % K
			d[n] += 1
		ans = 0
		for x in range(1, int((K + 1) / 2)):
			ans += max(d[x], d[K - x])
		if K % 2 == 0:
			if d[int(K / 2)] > 0:
				ans += 1
		if d[0] > 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		temp = [0] * K
		res = 0
		for i in arr:
			temp[i % K] += 1
		if temp[0]:
			res += 1
		l = 1
		r = K - 1
		while l < r:
			res += max(temp[l], temp[r])
			l += 1
			r -= 1
		if l == r and temp[l]:
			res += 1
		return res


class Solution:

	def maxGroupSize(self, arr, N, K):
		cnt = 0
		dp = [0] * K
		for v in arr:
			dp[v % K] += 1
		i = 0
		if dp[i] > 0:
			cnt += 1
		i += 1
		j = K - 1
		while i <= j:
			if i == j and dp[i] > 0:
				cnt += 1
				break
			cnt += max(dp[i], dp[j])
			i += 1
			j -= 1
		return cnt


from collections import defaultdict

def f(arr, si, c, n, k, l):
	if si >= n:
		return c
	flag = True
	for i in range(0, si):
		if arr[i] + arr[si] == k:
			flag = False
			break
	if flag:
		return f(arr, si + 1)

class Solution:

	def maxGroupSize(self, arr, N, K):
		a = [0] * K
		for r in arr:
			a[r % K] += 1
		ans = 0
		for i in range(1, (K + 1) // 2):
			ans += max(a[i], a[K - i])
		if K & 1 == 0 and a[K // 2] != 0:
			ans += 1
		if a[0] != 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		reminder_arr = [0] * K
		for i in arr:
			reminder = i % K
			reminder_arr[reminder] += 1
		count = 0
		for i in range(1, K // 2 + 1):
			if i != K - i:
				count += max(reminder_arr[i], reminder_arr[K - i])
			elif reminder_arr[i] > 0:
				count += 1
		if reminder_arr[0] > 0:
			count += 1
		return count


class Solution:

	def maxGroupSize(self, arr, N, K):
		dp = [0 for i in range(K)]
		for i in arr:
			dp[i % K] += 1
		i = 1
		j = K - 1
		ans = 0
		while i < j:
			ans += max(dp[i], dp[j])
			i += 1
			j -= 1
		if dp[0] > 0:
			ans += 1
		if i == j and dp[i] > 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, N, k):
		from collections import defaultdict as DD
		import math
		d = DD(int)
		for ele in arr:
			d[ele % k] += 1
		ans = 0
		if d[0]:
			ans += 1
		for i in range(1, k // 2 + 1):
			if i == k - i and d[i]:
				ans += 1
			else:
				ans += max(d[i], d[k - i])
		return ans


from collections import defaultdict

class Solution:

	def maxGroupSize(self, arr, N, K):
		mp = defaultdict(int)
		for i in arr:
			mp[i % K] += 1
		ans = 0
		if mp[0] != 0:
			ans += 1
		for i in range(1, K // 2 + 1):
			if i == K - i and mp[i] > 0:
				ans += 1
			else:
				ans += max(mp[i], mp[K - i])
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		rarr = [0 for i in range(K)]
		ans = 0
		for i in arr:
			rarr[i % K] += 1
		if K % 2 == 0:
			rarr[K // 2] = min(rarr[K // 2], 1)
		for i in range(1, (K + 2) // 2):
			ans += max(rarr[i], rarr[K - i])
		ans += min(rarr[0], 1)
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		dp = [0] * K
		res = 0
		for val in arr:
			dp[val % K] = dp[val % K] + 1
		i = 1
		j = K - 1
		while i < j:
			res = res + max(dp[i], dp[j])
			i = i + 1
			j = j - 1
		if dp[0] > 0:
			res = res + 1
		if i == j and dp[i] > 0:
			res = res + 1
		return res


class Solution:

	def maxGroupSize(self, arr, n, k):
		dp = [0] * k
		for ch in arr:
			dp[ch % k] += 1
		i = 1
		j = k - 1
		ans = 0
		while i < j:
			ans += max(dp[i], dp[j])
			i += 1
			j -= 1
		if dp[0] > 0:
			ans += 1
		if i == j and dp[i] > 0:
			ans += 1
		return ans


class Solution:

	def maxGroupSize(self, arr, n, k):
		l = [0] * k
		for i in arr:
			l[i % k] += 1
		res = 0
		i = 1
		j = K - 1
		while i < j:
			res += max(l[i], l[j])
			i += 1
			j -= 1
		if i == j and l[i] > 0:
			res += 1
		if l[0] > 0:
			res += 1
		return res


from collections import *

class Solution:

	def maxGroupSize(self, arr, N, k):
		HashMap = dict()
		for i in arr:
			HashMap[i % k] = 1 + HashMap.get(i % k, 0)
		res = 0
		l = 1
		r = k - 1
		while l < r:
			res += max(HashMap.get(l, 0), HashMap.get(r, 0))
			l += 1
			r -= 1
		if l == r and HashMap.get(l, 0) > 0:
			res += 1
		if HashMap.get(0, 0) > 0:
			res += 1
		return res


class Solution:

	def maxGroupSize(self, arr, N, K):
		d = [0] * K
		for i in arr:
			d[i % K] += 1
		res = 0
		for i in range(1, (K + 1) // 2):
			res += max(d[i], d[K - i])
		if K % 2 == 0 and d[K // 2]:
			res += 1
		if d[0]:
			res += 1
		return res


class Solution:

	def maxGroupSize(self, arr, N, k):
		ls = [0] * K
		for i in arr:
			x = i % k
			ls[x] += 1
		st = 1
		end = k - 1
		ct = 0
		while st < end:
			ct += max(ls[st], ls[end])
			st += 1
			end -= 1
		if st == end and ls[st] > 0:
			ct += 1
		if ls[0] > 0:
			ct += 1
		return ct


class Solution:

	def maxGroupSize(self, arr, N, k):
		ak = [0 for i in range(k)]
		for i in arr:
			ak[i % k] += 1
		c = 0
		for i in range(1, (k + 1) // 2):
			c += max(ak[i], ak[k - i])
		if k & 1 == 0 and ak[k // 2]:
			c += 1
		if ak[0]:
			c += 1
		return c


class Solution:

	def maxGroupSize(self, arr, N, K):
		r = [0] * K
		for i in range(N):
			r[arr[i] % K] += 1
		ans = 0
		for i in range(K // 2 + 1):
			if i == 0 or i == K - i:
				if r[i] != 0:
					ans += 1
			else:
				ans += max(r[i], r[K - i])
		return ans


class Solution:

	def maxGroupSize(self, arr, N, K):
		mp = [0] * K
		for i in range(0, N):
			mp[arr[i] % K] += 1
		(l, h) = (1, K - 1)
		ans = 0
		while l <= h:
			if l == h and mp[l] > 0:
				ans += 1
				break
			ans += max(mp[l], mp[h])
			l += 1
			h -= 1
		if mp[0] > 0:
			ans += 1
		return ans