Given an array A[] and positive integer K, the task is to count total number of pairs in the array whose sum is divisible by K.
Example 1:
Input : 
A[] = {2, 2, 1, 7, 5, 3}, K = 4
Output : 5
Explanation : 
There are five pairs possible whose sum
is divisible by '4' i.e., (2, 2), 
(1, 7), (7, 5), (1, 3) and (5, 3)
Example 2:
Input : 
A[] = {5, 9, 36, 74, 52, 31, 42}, K = 3
Output : 7 
Explanation : 
There are seven pairs whose sum is divisible by 3, 
i.e, (9, 36), (9,42), (74, 52), (36, 42), (74, 31), 
(31, 5) and (5, 52).
Your task :
You don't have to read input or print anything. Your task is to complete the function countKdivPairs() which takes the array, it's size and an integer K as input and returns the count of pairs whose sum is divisible by K.
 
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(k)
 
Constraints :
1 <= N <=10^6
1 <= A[i] <= 10^6
1 <= K <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def countKdivPairs(self, arr, n, k):

        #code here

Solutions:
class Solution:

	def countKdivPairs(self, arr, n, k):
		ax = [0] * k
		for i in arr:
			ax[i % k] += 1
		res = 0
		for i in range(k // 2 + 1):
			if 2 * i == k or i == 0:
				res += ax[i] * (ax[i] - 1) // 2
			else:
				res += ax[i] * ax[k - i]
		return res


class Solution:

	def countKdivPairs(self, arr, n, k):
		m = [0] * k
		c = 0
		for i in range(n):
			rem = arr[i] % k
			if rem != 0:
				c += m[k - rem]
			else:
				c += m[0]
			m[rem] += 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		n = len(arr)
		pairs = 0
		freqArr = [0] * k
		for i in range(len(arr)):
			idx = arr[i] % k
			freqArr[idx] += 1
		x = freqArr[0]
		pairs += x * (x - 1) // 2
		if k % 2 == 0:
			x = freqArr[k // 2]
			pairs += x * (x - 1) // 2
		i = 1
		j = k - 1
		while i < j:
			x = freqArr[i]
			y = freqArr[j]
			pairs += x * y
			i += 1
			j -= 1
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		counter = [0] * k
		ans = 0
		for ele in arr:
			ele %= k
			ans += counter[(k - ele) % k]
			counter[ele] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		(d, count) = ({}, 0)
		for i in arr:
			rem = i % k
			if rem == 0:
				count += d.get(0, 0)
			else:
				count += d.get(k - rem, 0)
			d[rem] = d.get(rem, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		remainders = defaultdict(int)
		total = 0
		for i in range(len(arr)):
			curr = arr[i] % k
			if curr == 0 and 0 in remainders:
				total += remainders[0]
			elif k - curr in remainders:
				total += remainders[k - curr]
			remainders[arr[i] % k] += 1
		return total


class Solution:

	def countKdivPairs(self, arr, n, k):
		c = [0] * k
		for a in arr:
			c[a % k] += 1
		ans = 0
		for i in range(k):
			if k - i < i:
				continue
			if i + i == k or i == 0:
				ans += c[i] * (c[i] - 1) // 2
			else:
				ans += c[i] * c[k - i]
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		dic = [0] * k
		for i in arr:
			temp = i % k
			dic[temp] += 1
		s = dic[0] * (dic[0] - 1) // 2
		i = 1
		while i <= k // 2 and i != k - i:
			s += dic[i] * dic[k - i]
			i += 1
		if k % 2 == 0:
			s += dic[k // 2] * (dic[k // 2] - 1) // 2
		return s


from collections import Counter

class Solution:

	def countKdivPairs(self, arr, n, k):
		count = 0
		arr_rem = [x % k for x in arr]
		dict_rem = Counter(arr_rem)
		for i in range(0, int(k / 2) + 1):
			if i == k / 2 or i == 0:
				count += dict_rem[i] * (dict_rem[i] - 1) / 2
			else:
				count += dict_rem[i] * dict_rem[k - i]
			i += 1
		return int(count)


class Solution:

	def countKdivPairs(self, arr, n, k):
		d = {}
		for i in range(n):
			if a[i] % k not in d.keys():
				d[a[i] % k] = 1
			else:
				d[a[i] % k] += 1
		ans = 0
		ans1 = 0
		for i in d.keys():
			if i == 0 or i == k - i:
				ans += d[i] * (d[i] - 1) // 2
			elif k - i in d.keys():
				ans1 += d[i] * d[k - i]
		return ans + ans1 // 2


class Solution:

	def countKdivPairs(self, arr, n, k):
		for i in range(len(arr)):
			arr[i] = arr[i] % k
		past = {0: 0}
		ans = 0
		for i in range(len(arr)):
			if k - arr[i] in past:
				ans += past[k - arr[i]]
			elif arr[i] == 0:
				ans += past[0]
			if arr[i] in past:
				past[arr[i]] += 1
			else:
				past[arr[i]] = 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		c = 0
		d = {}
		su = 0
		for i in arr:
			x = i % k
			if x == 0:
				c += d.get(0, 0)
			else:
				c += d.get(k - x, 0)
			d[x] = d.get(x, 0) + 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		freq = [0] * k
		for i in arr:
			freq[i % k] += 1
		ans = 0
		for i in range(1, k // 2 + 1):
			j = k - i
			if i == j:
				ans += freq[i] * (freq[i] - 1) // 2
			else:
				ans += freq[i] * freq[j]
		ans += freq[0] * (freq[0] - 1) // 2
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		a = [0] * k
		for i in range(n):
			a[arr[i] % k] += 1
		ans = 0
		for i in range(k):
			if i > k - i:
				break
			elif i == k - i or i == 0:
				ans += a[i] * (a[i] - 1) // 2
			else:
				ans += a[i] * a[k - i]
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		s = [0] * k
		for i in range(n):
			s[arr[i] % k] += 1
		count = s[0] * (s[0] - 1) / 2
		i = 1
		while i <= k // 2 and i != k - i:
			count += s[i] * s[k - i]
			i += 1
		if k % 2 == 0:
			count += s[k // 2] * (s[k // 2] - 1) / 2
		return int(count)


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		dic = defaultdict(int)
		res = 0
		for i in arr:
			rem = i % k
			if rem != 0:
				res += dic[k - rem]
			else:
				res += dic[0]
			dic[rem] += 1
		return res


import collections

class Solution:

	def countKdivPairs(self, arr, n, k):
		pairs = 0
		dic = collections.defaultdict(int)
		for i in range(len(arr)):
			rem = arr[i] % k
			comp = k - rem
			if rem != 0:
				pairs += dic[comp]
			else:
				pairs += dic[0]
			dic[rem] += 1
		return pairs


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		hmap = defaultdict(int)
		count = 0
		for ele in arr:
			key = ele % k
			if key == 0:
				count += hmap[0]
			else:
				count += hmap[k - key]
			hmap[key] += 1
		return count


class Solution:

	def countKdivPairs(self, arr, n, k):
		d = [0 for i in range(k)]
		c = 0
		for i in range(n):
			r = arr[i] % k
			c += d[(k - r) % k]
			d[r] += 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		dp = [0 for i in range(k)]
		c = 0
		for i in range(n):
			ri = arr[i] % k
			c += dp[(k - ri) % k]
			dp[ri] += 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		freq = [0] * k
		count_pairs = 0
		for num in arr:
			mod = num % k
			count_pairs += freq[(k - mod) % k]
			freq[mod] += 1
		return count_pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		memo = dict()
		for i in range(k):
			memo[i] = 0
		for i in range(n):
			arr[i] %= k
			memo[arr[i]] = memo.get(arr[i], 0) + 1
		res = 0
		for i in range(n):
			if arr[i] == 0:
				res += memo[0] - 1
			else:
				dif = k - arr[i]
				res += memo[dif]
				if dif == arr[i]:
					res -= 1
		return res // 2


class Solution:

	def countKdivPairs(self, arr, n, k):
		remainders = {}
		remainders[0] = 0
		count = 0
		for val in arr:
			remainder = val % k
			if remainder == 0:
				count += remainders[0]
			elif k - remainder in remainders:
				count += remainders[k - remainder]
			if remainder in remainders:
				remainders[remainder] += 1
			else:
				remainders[remainder] = 1
		return count


class Solution:

	def countKdivPairs(self, arr, n, k):
		d = {}
		ans = 0
		for i in range(n):
			reminder = arr[i] % k
			if reminder != 0:
				ans = ans + d.get(k - reminder, 0)
			else:
				ans += d.get(0, 0)
			d[reminder] = d.get(reminder, 0) + 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		d = {}
		for i in arr:
			current = i % k
			target = k - current
			if current == 0:
				ans += d.get(current, 0)
			else:
				ans += d.get(target, 0)
			d[current] = 1 + d.get(current, 0)
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		d = {}
		for i in arr:
			c = i % k
			find = k - c
			if c != 0:
				ans += d.get(find, 0)
			else:
				ans += d.get(0, 0)
			d[c] = 1 + d.get(c, 0)
		return ans


class Solution:

	def countKdivPairs(self, nums, n, k):
		d = {}
		count = 0
		for i in nums:
			rem = i % k
			req = k - i % k
			if rem == 0:
				req = 0
			if req in d:
				count += d[req]
			if i % k in d:
				d[i % k] += 1
			else:
				d[i % k] = 1
		return count


class Solution:

	def countKdivPairs(self, nums, n, k):
		(hashMap, c, rem) = ({}, 0, 0)
		for i in range(n):
			rem = nums[i] % k
			c += hashMap.get((k - rem) % k, 0)
			hashMap[rem] = hashMap.get(rem, 0) + 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		occ = [0 for i in range(k)]
		c = 0
		for i in range(n):
			rem = arr[i] % k
			c += occ[(k - rem) % k]
			occ[rem] += 1
		return c


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		d = dict()
		for i in range(n):
			rem1 = arr[i] % k
			if rem1 != 0:
				if k - rem1 in d:
					ans = ans + d[k - rem1]
			elif 0 in d:
				ans = ans + d[0]
			if rem1 not in d:
				d[rem1] = 1
			else:
				d[rem1] = d[rem1] + 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		f = [0] * k
		for i in range(n):
			f[arr[i] % k] += 1
		op = f[0] * (f[0] - 1) / 2
		if k % 2 == 0:
			op += f[k // 2] * (f[k // 2] - 1) / 2
		i = 1
		while i <= k // 2 and i != k - i:
			op += f[i] * f[k - i]
			i += 1
		return int(op)


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		m = {0: 0}
		for i in range(n):
			mod = arr[i] % k
			if mod == 0:
				ans = ans + m[0]
			if k - mod in m:
				ans = ans + m[k - mod]
			if mod not in m:
				m[mod] = 1
			else:
				m[mod] += 1
		return ans


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		has = defaultdict(int)
		ans = 0
		for num in arr:
			temp = num % k
			if temp == 0:
				ans += has[temp]
			else:
				ans += has[k - temp]
			has[temp] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		hm = {}
		for ele in arr:
			curr = ele % k
			if curr == 0 and 0 in hm:
				ans += hm[0]
			else:
				comple = k - curr
				if comple in hm:
					ans += hm[comple]
			hm[curr] = 1 + hm.get(curr, 0)
		return ans


class Solution:

	def countKdivPairs(self, arr, n, x):
		d = {}
		co = 0
		for i in arr:
			k = i % x
			if x - k in d:
				co += d[x - k]
			if k == 0:
				if 0 in d:
					co += d[0]
			if k not in d:
				d[k] = 1
			else:
				d[k] += 1
		return co


class Solution:

	def countKdivPairs(self, arr, n, k):
		rem = [0] * k
		ans = 0
		for i in range(n):
			rem[arr[i] % k] += 1
		ans += rem[0] * (rem[0] - 1) // 2
		for i in range(1, k // 2):
			ans += rem[i] * rem[k - i]
		if k % 2 == 0:
			ans += rem[k // 2] * (rem[k // 2] - 1) // 2
		elif k // 2 + 1 < k:
			ans += rem[k // 2] * rem[k // 2 + 1]
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		remainders = [0] * k
		for num in arr:
			remainder = num % k
			remainders[remainder] += 1
		pairs = remainders[0] * (remainders[0] - 1) // 2
		for i in range(1, k // 2 + 1):
			if i == k - i:
				break
			new_pairs = remainders[i] * remainders[k - i]
			pairs += new_pairs
		if k % 2 == 0:
			temp = remainders[k // 2]
			pairs += temp * (temp - 1) // 2
		return pairs


from collections import Counter

class Solution:

	def countKdivPairs(self, arr, n, k):
		for i in range(n):
			arr[i] = arr[i] % k
		c = Counter(arr)
		count = 0
		for item in c:
			if item * 2 == k or item == 0:
				count += c[item] * (c[item] - 1) // 2
				continue
			if k - item in c:
				count += c[item] * c[k - item] / 2
		return int(count)


class Solution:

	def countKdivPairs(self, arr, n, k):
		d = {}
		for i in arr:
			if i % k not in d:
				d[i % k] = 1
			else:
				d[i % k] += 1
		r = 0
		if 0 in d:
			r += d[0] * (d[0] - 1) // 2
		for x in d:
			if x == k - x:
				r += d[x] * (d[x] - 1) // 2
			elif k - x in d:
				r += d[k - x] * d[x]
				d[x] = 0
		return r


class Solution:

	def countKdivPairs(self, A, n, K):
		freq = [0] * K
		for i in range(n):
			freq[A[i] % K] += 1
		sum = freq[0] * (freq[0] - 1) / 2
		i = 1
		while i <= K // 2 and i != K - i:
			sum += freq[i] * freq[K - i]
			i += 1
		if K % 2 == 0:
			sum += freq[K // 2] * (freq[K // 2] - 1) / 2
		return int(sum)


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		hash_map = defaultdict(int)
		count = 0
		for i in range(len(arr)):
			remainder = arr[i] % k
			complement = k - remainder
			if complement == k:
				count += hash_map[0]
			if complement in hash_map:
				count += hash_map[complement]
			hash_map[remainder] += 1
		return count


import collections

class Solution:

	def countKdivPairs(self, arr, n, k):
		rem_freq = collections.defaultdict(int)
		count = 0
		for i in arr:
			rem = i % k
			count += rem_freq[k - rem]
			rem_freq[rem if rem != 0 else k] += 1
		return count


from collections import defaultdict

class Solution:

	def countKdivPairs(self, nums, n, k):
		has = defaultdict(lambda : 0)
		ans = 0
		for i in range(len(nums)):
			rem1 = nums[i] % k
			if rem1 != 0:
				ans += has[k - rem1]
			else:
				ans += has[0]
			has[rem1] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		arr = [i % k for i in arr]
		from collections import Counter
		c = Counter(arr)
		ans = 0
		for i in range(k // 2 + 1):
			if k % 2 == 0 and i == k // 2 or i == 0:
				ans += c[i] * (c[i] - 1) // 2
			else:
				ans += c[i] * c[k - i]
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		divs = {i: 0 for i in range(k)}
		pairs = 0
		for el in arr:
			mod = el % k
			pairs += divs[(k - mod) % k]
			divs[mod] += 1
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		m = dict()
		pairs = 0
		for i in arr:
			rem = i % k
			if rem != 0:
				pairs += m.get(k - rem, 0)
			else:
				pairs += m.get(0, 0)
			m[rem] = m.get(rem, 0) + 1
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		d = {}
		ans = 0
		for i in arr:
			r = i % k
			if r == 0:
				if 0 in d:
					ans += d[0]
			elif k - r in d:
				ans += d[k - r]
			if r in d:
				d[r] += 1
			else:
				d[r] = 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		from collections import defaultdict
		re = defaultdict(int)
		cnt = 0
		for ele in arr:
			rem = ele % k
			tar = (k - rem) % k
			cnt += re[tar]
			re[rem] += 1
		return cnt


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		lst = [0 for i in range(k)]
		for i in range(n):
			rem = arr[i] % k
			ans += lst[(k - rem) % k]
			lst[rem] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		arrRemainder = [0] * k
		for i in range(n):
			arrRemainder[arr[i] % k] += 1
		pairCount = arrRemainder[0] * (arrRemainder[0] - 1) // 2
		if k % 2 == 0:
			pairCount += arrRemainder[k // 2] * (arrRemainder[k // 2] - 1) // 2
			stop = k // 2
		else:
			stop = k // 2 + 1
		for i in range(1, stop, 1):
			pairCount += arrRemainder[i] * arrRemainder[k - i]
		return pairCount


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		remain_freq = defaultdict(int)
		ret = 0
		for num in arr:
			remain = num % k
			if remain == 0:
				ret += remain_freq[0]
			else:
				ret += remain_freq[k - remain]
			remain_freq[remain] += 1
		return ret


class Solution:

	def countKdivPairs(self, l, n, k):
		freq = {}
		ct = 0
		for v in l:
			md = v % k
			if md != 0:
				if k - md in freq:
					ct += freq[k - md]
			elif md in freq:
				ct += freq[md]
			if md in freq:
				freq[md] += 1
			else:
				freq[md] = 1
		return ct


import collections

class Solution:

	def countKdivPairs(self, arr, n, k):
		(lookup, pairs) = (collections.defaultdict(int), 0)
		for i in arr:
			remainder = i % k
			if remainder == 0:
				pairs += lookup[0]
			else:
				pairs += lookup[k - remainder]
			lookup[remainder] += 1
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		(lookup, pairs) = ({}, 0)
		for i in arr:
			remainder = i % k
			if remainder == 0 and remainder in lookup:
				pairs += lookup[0]
			elif k - remainder in lookup:
				pairs += lookup[k - remainder]
			if remainder not in lookup:
				lookup[remainder] = 1
			else:
				lookup[remainder] += 1
		return pairs


class Solution:

	def countKdivPairs(self, A, n, K):
		d = {}
		res = 0
		for i in A:
			rem = i % K
			diff = K - rem if rem else rem
			res += d.get(diff, 0)
			d[rem] = 1 + d.get(rem, 0)
		return res


class Solution:

	def countKdivPairs(self, A, n, K):
		d = {}
		pairs = 0
		for song in A:
			rem = song % K
			diff = K - rem if rem else rem
			pairs += d.get(diff, 0)
			d[rem] = 1 + d.get(rem, 0)
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		pairs = 0
		d = {i: 0 for i in range(k)}
		for ele in arr:
			mod = ele % k
			pairs += d[(k - mod) % k]
			d[mod] += 1
		return pairs


class Solution:

	def countKdivPairs(self, arr, n, k):
		h = {i: 0 for i in range(k)}
		res = 0
		for x in arr:
			t = x % k
			y = (k - x) % k
			res += h[y]
			h[t] += 1
		return res


class Solution:

	def countKdivPairs(self, arr, n, k):
		ans = 0
		remainderMap = [0] * k
		for num in arr:
			remainder = num % k
			if remainder != 0:
				ans += remainderMap[k - remainder]
			else:
				ans += remainderMap[0]
			remainderMap[remainder] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		mp = {i: 0 for i in range(k)}
		ans = 0
		for i in range(n):
			rem = arr[i] % k
			if rem != 0:
				ans += mp[k - arr[i] % k]
			else:
				ans += mp[0]
			mp[rem] = mp.get(rem, 0) + 1
		return ans


from collections import defaultdict

class Solution:

	def countKdivPairs(self, arr, n, k):
		d = defaultdict(int)
		ans = 0
		for i in arr:
			r = i % k
			if r != 0:
				ans += d[k - r]
			else:
				ans += d[0]
			d[r] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		freq = [0] * k
		for i in range(n):
			freq[arr[i] % k] += 1
		sum = freq[0] * (freq[0] - 1) / 2
		i = 1
		while i <= k // 2 and i != k - i:
			sum += freq[i] * freq[k - i]
			i += 1
		if k % 2 == 0:
			sum += freq[k // 2] * (freq[k // 2] - 1) / 2
		return int(sum)


import collections

class Solution:

	def countKdivPairs(self, arr, n, k):
		res = 0
		remain_freq = collections.defaultdict(int)
		for (idx, val) in enumerate(arr):
			remainder = val % k
			if remainder != 0:
				comp = k - remainder
			else:
				comp = 0
			if comp in remain_freq:
				res += remain_freq[comp]
				remain_freq[remainder] += 1
			else:
				remain_freq[remainder] += 1
		return res


class Solution:

	def countKdivPairs(self, arr, n, k):
		dic = {}
		count = 0
		for i in arr:
			rem = i % k
			if rem != 0:
				if k - rem in dic:
					count += dic[k - rem]
			elif rem in dic:
				count += dic[rem]
			if rem in dic:
				dic[rem] += 1
			else:
				dic[rem] = 1
		return count


from collections import Counter

class Solution:

	def countKdivPairs(self, arr, n, k):
		for i in range(n):
			arr[i] %= k
		mp = {}
		ans = 0
		for i in arr:
			if i == 0:
				if i in mp:
					ans += mp[i]
			elif k - i in mp:
				ans += mp[k - i]
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		return ans


class Solution:

	def countKdivPairs(self, arr, n, k):
		count_remainder = [0] * k
		for num in arr:
			remainder = num % k
			count_remainder[remainder] += 1
		answer = 0
		answer += count_remainder[0] * (count_remainder[0] - 1) // 2
		for i in range(1, k // 2):
			answer += count_remainder[i] * count_remainder[k - i]
		if k % 2 != 0 and 0 <= k - k // 2 < k:
			answer += count_remainder[k // 2] * count_remainder[k - k // 2]
		if k % 2 == 0:
			answer += count_remainder[k // 2] * (count_remainder[k // 2] - 1) // 2
		return answer


class Solution:

	def countKdivPairs(self, arr, n, k):
		mp = [0] * k
		for i in range(n):
			mp[arr[i] % k] += 1
		res = int(mp[0] * (mp[0] - 1) / 2)
		if k % 2 == 0:
			for i in range(1, int(k / 2)):
				res += mp[i] * mp[k - i]
			res += int(mp[int(k / 2)] * (mp[int(k / 2)] - 1) / 2)
		else:
			for i in range(1, int(k / 2) + 1):
				res += mp[i] * mp[k - i]
		return res


class Solution:

	def countKdivPairs(self, arr, n, k):
		k_map = {}
		for i in range(k):
			k_map[i] = 0
		for num in arr:
			k_map[num % k] += 1
		count = 0
		for num in arr:
			if num % k == 0:
				count += k_map[0] - 1
			elif num % k == k - num % k:
				count += k_map[num % k] - 1
			else:
				count += k_map[k - num % k]
		return count // 2


class Solution:

	def countKdivPairs(self, arr, n, k):
		for i in range(n):
			arr[i] = arr[i] % k
		freq = {i: 0 for i in arr}
		res = 0
		for i in arr:
			j = k - i
			if j == k and 0 in freq.keys():
				res += freq[0]
			elif j in freq.keys():
				res += freq[j]
			freq[i] += 1
		return res


class Solution:

	def countKdivPairs(self, A, n, B):
		d = {}
		ans = 0
		for i in range(len(A)):
			rem = A[i] % B
			if rem != 0:
				ans += d.get(B - A[i] % B, 0)
			else:
				ans += d.get(0, 0)
			if rem in d:
				d[rem] += 1
			else:
				d[rem] = 1
		return ans