Given an array of integers of size n and an integer k, find all the pairs in the array whose absolute difference is divisible by k.
Example 1:
Input:
n = 3
arr[] = {3, 7, 11}
k = 4
Output:
3
Explanation:
(11-3) = 8 is divisible by 4
(11-7) = 4 is divisible by 4
(7-3) = 4 is divisible by 4
Example 2:
Input:
n = 4
arr[] = {1, 2, 3, 4}
k = 2
Output :
2
Explanation:
Valid pairs are (1,3), and (2,4).
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countPairs() which takes integers n, array arr[ ], integer k as input parameters and returns the number of pairs whose absolute difference is divisible by k.
Note: The answer may be large so use 64-bit integer. 
Expected Time Complexity: O(n + k)
Expected Auxiliary Space: O(k)
Constraints:
2 ≤ n ≤ 10^{5}
1 ≤ k,arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

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

        # code here

Solutions:
class Solution:

	def countPairs(self, n, arr, k):
		modDic = {}
		result = 0
		for item in arr:
			resToCheck = item % k
			inDic = resToCheck in modDic
			if inDic:
				modDic[resToCheck] = modDic[resToCheck] + 1
			else:
				modDic[resToCheck] = 1
		for item in modDic:
			result += modDic[item] * (modDic[item] - 1) // 2
		return result


class Solution:

	def countPairs(self, n, arr, k):
		dict = {}
		cnt = 0
		for i in arr:
			num = i % k
			if num in dict:
				dict[num] += 1
				cnt += dict[num]
			else:
				dict[num] = 0
		return cnt


class Solution:

	def countPairs(self, n, arr, k):
		cnt = 0
		for i in range(n):
			arr[i] = (arr[i] + k) % k
		hash = [0] * k
		for i in range(n):
			hash[arr[i]] += 1
		for i in range(k):
			cnt += hash[i] * (hash[i] - 1) // 2
		return cnt


class Solution:

	def countPairs(self, n, arr, k):
		d = {}
		ans = 0
		for i in arr:
			if i % k in d:
				d[i % k] += 1
			else:
				d[i % k] = 1
		for i in d:
			if d[i] > 1:
				ans = ans + d[i] * (d[i] - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		rem = []
		for elem in arr:
			rem.append(elem % k)
		freq = [0 for _ in range(k)]
		for elem in rem:
			freq[elem] += 1
		pair = 0
		for index in range(k):
			pair += freq[index] * (freq[index] - 1) // 2
		return pair


class Solution:

	def countPairs(self, n, arr, k):
		rem = [0] * k
		for i in range(n):
			rem[arr[i] % k] += 1
		res = 0
		for i in range(k):
			res += rem[i] * (rem[i] - 1) // 2
		return res


class Solution:

	def countPairs(self, n, arr, k):
		dp = [0 for i in range(k)]
		s = 0
		for i in arr:
			s += dp[i % k]
			dp[i % k] += 1
		return s


class Solution:

	def countPairs(self, n, arr, k):
		freq = {}
		for val in arr:
			if val % k in freq:
				freq[val % k] += 1
			else:
				freq[val % k] = 1
		count = 0
		for val in freq:
			count += freq[val] * (freq[val] - 1) // 2
		return count


from collections import Counter
import math

class Solution:

	def countPairs(self, n, arr, k):
		ans = 0
		dp = [0 for _ in range(k)]
		for num in arr:
			rem = num % k
			ans += dp[rem]
			dp[rem] += 1
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		counts = {}
		for i in range(n):
			arr[i] %= k
			if arr[i] in counts:
				counts[arr[i]] += 1
			else:
				counts[arr[i]] = 1
		ans = 0
		for a in arr:
			counts[a] -= 1
			ans += counts[a]
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		dic = {}
		c = 0
		for i in arr:
			mod = i % k
			if mod in dic:
				c += dic[mod]
			else:
				dic[mod] = 0
			dic[mod] += 1
		return c


class Solution:

	def countPairs(self, n, arr, k):
		map = {}
		for i in arr:
			if i % k in map:
				map[i % k] += 1
			else:
				map[i % k] = 1
		count = 0
		for key in map:
			size = map[key]
			if size > 1:
				count += size * (size - 1) // 2
		return count


from collections import Counter

class Solution:

	def countPairs(self, n, arr, k):
		a = []
		for i in range(len(arr)):
			ele = arr[i] % k
			a.append(ele)
		c = Counter(a)
		s = 0
		for j in c:
			e = c[j] * (c[j] - 1) // 2
			s += e
		return s


class Solution:

	def countPairs(self, n, arr, k):
		dict1 = {}
		count = 0
		for i in arr:
			if i % k in dict1:
				dict1[i % k] += 1
			else:
				dict1[i % k] = 1
		for i in dict1:
			if dict1[i] > 1:
				count += dict1[i] * (dict1[i] - 1) // 2
		return count


class Solution:

	def countPairs(self, n, arr, k):
		h = [0 for i in range(k)]
		for i in arr:
			h[i % k] += 1
		ans = 0
		for i in h:
			if i != 0:
				ans += i * (i - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		make = [0] * k
		ans = 0
		for i in arr:
			make[i % k] += 1
		for i in make:
			ans += i * (i - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, a, k):
		d = {}
		for i in range(n):
			x = a[i] % k
			if x not in d:
				d[x] = 1
			else:
				d[x] += 1
		count = 0
		for i in d:
			count += d[i] * (d[i] - 1) // 2
		return count


class Solution:

	def countPairs(self, n, arr, k):
		s = 0
		d = dict()
		for i in arr:
			if i % k not in d:
				d[i % k] = 1
			else:
				d[i % k] += 1
		for i in d:
			s = s + d[i] * (d[i] - 1) // 2
		return s


class Solution:

	def countPairs(self, n, arr, k):
		dic = {}
		for ele in arr:
			dic[ele % k] = dic.get(ele % k, 0) + 1
		count = 0
		for ele in dic:
			count += dic[ele] * (dic[ele] - 1) // 2
		return count


class Solution:

	def countPairs(self, n, arr, k):
		i = 0
		j = 0
		l = 0
		for i in range(0, len(arr)):
			arr[i] = arr[i] % k
		d = {}
		for i in range(0, len(arr)):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] = d[arr[i]] + 1
		for i in d:
			if i in d:
				l = l + int(d[i] * (d[i] - 1) / 2)
		return l


class Solution:

	def countPairs(self, n, arr, k):
		dic = {}
		count = 0
		for ele in arr:
			num = ele % k
			if num in dic:
				dic[num] += 1
				count += dic[num]
			else:
				dic[num] = 0
		return count


from collections import Counter

class Solution:

	def countPairs(self, n, arr, k):
		u = []
		for j in range(len(arr)):
			y = arr[j] % k
			u.append(y)
		z = Counter(u)
		s = 0
		for h in z:
			e = z[h] * (z[h] - 1) // 2
			s = s + e
		return s


class Solution:

	def countPairs(self, n, arr, k):
		h = {}
		ans = 0
		for i in arr:
			temp = i % k
			if temp not in h:
				h[temp] = 1
			else:
				h[temp] += 1
		temp = 0
		for j in arr:
			i = j % k
			temp = k - i
			if h[i] >= 2:
				ans += h[i] - 1
				h[i] = h[i] - 1
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		d = {}
		count = 0
		for i in arr:
			num = i % k
			if num in d:
				d[num] += 1
				count += d[num]
			else:
				d[num] = 0
		return count


class Solution:

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


class Solution:

	def countPairs(self, n, arr, k):
		rem = [0] * k
		ans = 0
		for item in arr:
			rem[item % k] += 1
		for i in range(k):
			ans += rem[i] * (rem[i] - 1) / 2
		return int(ans)


class Solution:

	def countPairs(self, n, arr, k):
		l = [0] * k
		c = 0
		for i in arr:
			c += l[i % k]
			l[i % k] += 1
		return c


from collections import defaultdict

class Solution:

	def countPairs(self, n, arr, k):
		rem = defaultdict(list)
		for num in arr:
			rem[num % k].append(num)
		ans = 0
		for (k, grp) in rem.items():
			lgt = len(grp)
			ans += lgt * (lgt - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		ans = 0
		mod = [[] for size in range(k)]
		for i in range(n):
			mod[arr[i] % k].append(arr[i])
		for i in range(k):
			ans += len(mod[i]) * (len(mod[i]) - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, A, k):
		dp = [0] * k
		ans = 0
		for i in A:
			ans += dp[i % k]
			dp[i % k] += 1
		return ans


class Solution:

	def countPairs(self, n, a, k):
		mp = {}
		s = 0
		for i in range(len(a)):
			if a[i] % k not in mp:
				mp[a[i] % k] = 1
			else:
				s += mp[a[i] % k]
				mp[a[i] % k] += 1
		return s


class Solution:

	def countPairs(self, n, arr, k):
		m = {}
		for i in arr:
			m[i % k] = m.get(i % k, 0) + 1
		ans = 0
		for i in m:
			if m[i] > 1:
				ans += m[i] * (m[i] - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		freq = [0] * k
		for i in range(n):
			freq[arr[i] % k] += 1
		count = 0
		for i in range(k):
			count += freq[i] * (freq[i] - 1) // 2
		return count


class Solution:

	def countPairs(self, n, arr, k):
		dic = {}
		cnt = 0
		for i in arr:
			q = i % k
			if q not in dic:
				dic[q] = 0
			else:
				dic[q] += 1
				cnt += dic[q]
		return cnt


class Solution:

	def countPairs(self, n, arr, k):
		lookup = {}
		ans = 0
		for e in arr:
			num = e % k
			if num in lookup:
				lookup[num] += 1
				ans += lookup[num]
			else:
				lookup[num] = 0
		return ans


class Solution:

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


class Solution:

	def countPairs(self, n, arr, k):
		d = [0] * (k + 1)
		c = 0
		for i in range(len(arr)):
			arr[i] %= k
			d[arr[i]] += 1
		for i in d:
			c += i * (i - 1) // 2
		return c


class Solution:

	def countPairs(self, n, arr, k):
		count = 0
		for i in range(len(arr)):
			arr[i] = arr[i] % k
		hash = [0] * k
		for i in range(len(arr)):
			hash[arr[i]] += 1
		for i in hash:
			count += i * (i - 1) / 2
		return int(count)


class Solution:

	def countPairs(self, n, arr, k):
		count = 0
		rem = [0] * k
		for no in arr:
			rem[no % k] += 1
		for no in rem:
			if no != 0:
				count += no * (no - 1) // 2
		return count


class Solution:

	def countPairs(self, n, arr, k):
		count = 0
		c_k = [0] * k
		for i in arr:
			c_k[i % k] += 1
		for num in c_k:
			count += int(num * (num - 1) / 2)
		return count


class Solution:

	def countPairs(self, n, arr, k):
		c = 0
		d = {}
		for i in arr:
			s = i % k
			if s in d:
				d[s] += 1
				c += d[s]
			else:
				d[s] = 0
		return c


class Solution:

	def countPairs(self, n, arr, k):
		inp = 0
		p = [0] * k
		for a in arr:
			i = a % k
			p[i] = p[i] + 1
		for x in range(0, k):
			inp = inp + p[x] * (p[x] - 1)
		return int(inp / 2)


class Solution:

	def countPairs(self, n, arr, k):
		inc = 0
		c = [0] * k
		for a in arr:
			i = a % k
			c[i] = c[i] + 1
		for x in range(0, k):
			inc = inc + c[x] * (c[x] - 1)
		return int(inc / 2)


class Solution:

	def countPairs(self, n, arr, k):
		ans = 0
		m = {}
		for el in arr:
			if el % k in m:
				ans = ans + m[el % k]
				m[el % k] += 1
			else:
				m[el % k] = 1
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		s = [0] * k
		for i in arr:
			s[i % k] += 1
		res = 0
		for i in s:
			if i:
				res += i * (i - 1) // 2
		return res


class Solution:

	def countPairs(self, n, arr, k):
		d = {}
		ctr = 0
		for e in arr:
			n = e % k
			if n in d:
				d[n] = d[n] + 1
				ctr += d[n]
			else:
				d[n] = 0
		return ctr


class Solution:

	def countPairs(self, n, arr, k):
		yo = dict()
		for i in arr:
			t = i % k
			if t not in yo:
				yo[t] = 1
			else:
				yo[t] += 1
		m = 0
		for j in yo.values():
			m += int(j * (j - 1) / 2)
		return m


from collections import Counter

class Solution:

	def countPairs(self, n, arr, k):
		c = 0
		l = []
		for i in arr:
			l.append(i % k)
		d = Counter(l)
		for (k, v) in d.items():
			c += v * (v - 1) // 2
		return c


from collections import defaultdict

class Solution:

	def countPairs(self, n, arr, k):
		d = defaultdict(lambda : 0)
		ans = 0
		for i in arr:
			d[(i + k) % k] += 1
		for i in range(k):
			ans += d[i] * (d[i] - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		dic = [0] * k
		for i in range(n):
			mod = arr[i] % k
			dic[mod] += 1
		ans = 0
		for i in dic:
			ans += i * (i - 1) / 2
		return int(ans)


class Solution:

	def countPairs(self, n, arr, k):
		d = {}
		a = 0
		for h in arr:
			o = h % k
			if o not in d:
				d[o] = 1
			else:
				d[o] += 1
		for h in d:
			if d[h] > 1:
				a += d[h] * (d[h] - 1) // 2
		return a


class Solution:

	def countPairs(self, n, arr, k):
		dic = {}
		count = 0
		for i in range(len(arr)):
			if arr[i] % k in dic:
				count = count + dic[arr[i] % k]
				dic[arr[i] % k] = dic[arr[i] % k] + 1
			else:
				dic[arr[i] % k] = 1
		return count


from collections import Counter

class Solution:

	def countPairs(self, n, arr, k):
		a = [i % k for i in arr]
		c = Counter(a)
		ans = 0
		for i in range(k):
			x = c[i]
			ans += x * (x - 1) // 2
		return ans


class Solution:

	def countPairs(self, n, arr, k):
		count = 0
		new = [0] * k
		for i in range(n):
			count += new[arr[i] % k]
			new[arr[i] % k] += 1
		return count


class Solution:

	def countPairs(self, n, arr, k):
		dp = [0] * k
		for v in arr:
			dp[v % k] += 1
		res = 0
		for r in dp:
			res += r * (r - 1) // 2
		return res