Given an array Arr of N positive integers. Find the number of pairs of integers whose difference is equal to a given number K.
Note: (a, b) and (b, a) are considered same. Also, same numbers at different indices are considered different.
Example 1:
Input: 
N = 5
Arr[] = {1, 5, 3, 4, 2}
K = 3
Output: 2
Explanation: There are 2 pairs with difference 3, 
             the pairs are {1, 4} and {5, 2} 
Example 2:
Input: 
N = 6
Arr[] = {8, 12, 16, 4, 0, 20}
K = 4
Output: 5
Explanation: There are 5 pairs with difference 4, 
             the pairs are {0, 4}, {4, 8}, 
             {8, 12}, {12, 16} and {16, 20} 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countPairsWithDiffK() which takes the array arr[], n and k as inputs and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(max(Arr_{i}))
Constraints:
1 <= N <= 10^{5}
0 <= K <= 10^{5}
0 <= Arr_{i} <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3
class Solution:

	
	def countPairsWithDiffK(self,arr, n, k):
    	# code here



Solutions:
import math

def binomial(x, y):
	try:
		return math.factorial(x) // math.factorial(y) // math.factorial(x - y)
	except ValueError:
		return 0

class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		res = 0
		mapp = {}
		for a in arr:
			if a not in mapp:
				mapp[a] = 1
			else:
				mapp[a] += 1
		if k == 0:
			for i in sorted(mapp):
				if mapp[i] > 1:
					res += binomial(mapp[i], 2)
		else:
			for i in sorted(mapp):
				if i + k in mapp:
					res += mapp[i] * mapp[i + k]
		return res


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		freq = {}
		c = 0
		if k == 0:
			for i in arr:
				if i not in freq:
					freq[i] = 0
				freq[i] += 1
			for i in freq:
				c += freq[i] * (freq[i] - 1) // 2
			return c
		for i in range(n):
			if k + arr[i] in freq:
				c += freq[k + arr[i]]
			if arr[i] - k in freq:
				c += freq[arr[i] - k]
			if arr[i] not in freq:
				freq[arr[i]] = 0
			freq[arr[i]] += 1
		return c


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		lis = arr.copy()
		lis = list(set(lis))
		dic = {}
		ans = 0
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		if k == 0:
			for i in lis:
				if dic[i] > 1:
					ans += dic[i] * (dic[i] - 1) // 2
			return ans
		else:
			for i in arr:
				if i + k in dic:
					ans += dic[i + k]
			return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		d = dict()
		for i in arr:
			d[i] = 1 + d.get(i, 0)
		count = 0
		for i in range(n):
			a = arr[i]
			if k == 0:
				if d[a] > 1:
					d[a] -= 1
					count += d[a]
			elif a + k in d:
				count += d[a + k]
		return count


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		c = 0
		d = {}
		for x in arr:
			if x in d:
				d[x] += 1
			else:
				d[x] = 1
		if k == 0:
			for n in d:
				c += d[n] * (d[n] - 1) // 2
		else:
			for n in d:
				if n - k in d:
					c += d[n] * d[n - k]
		return c


from collections import defaultdict

class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		d = defaultdict(int)
		ans = 0
		for i in range(n):
			ans += d[arr[i] + k]
			ans += d[arr[i] - k]
			d[arr[i]] += 1
		if k == 0:
			return ans // 2
		return ans


from collections import Counter

class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		c = Counter(arr)
		count = 0
		if k == 0:
			for item in c:
				count += c[item] * (c[item] - 1) // 2
			return count
		for item in c:
			count += c[item] * c[item + k]
		return count


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		mapx = dict()
		arr.sort(reverse=True)
		ans = 0
		for i in range(n):
			if arr[i] + k in mapx:
				ans += mapx[arr[i] + k]
			if arr[i] not in mapx:
				mapx[arr[i]] = 1
			else:
				mapx[arr[i]] += 1
		return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		mapx = dict()
		ans = 0
		for i in range(n):
			if k + arr[i] in mapx:
				ans += mapx[k + arr[i]]
			if arr[i] not in mapx:
				mapx[arr[i]] = 1
			else:
				mapx[arr[i]] += 1
		mapx = dict()
		for i in range(n):
			if arr[i] in mapx:
				ans += mapx[arr[i]]
			if k + arr[i] not in mapx:
				mapx[k + arr[i]] = 1
			else:
				mapx[k + arr[i]] += 1
		if k == 0:
			return ans // 2
		return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		c = 0
		d = dict()
		for nums in arr:
			d[nums] = 1 + d.get(nums, 0)
		if k == 0:
			for nn in d:
				c += d[nn] * (d[nn] - 1) / 2
		else:
			for nn in d:
				if nn - k in d:
					c += d[nn - k] * d[nn]
		return int(c)


class Solution:

	def countPairsWithDiffK(self, nums, n, k):
		d = {}
		n = len(nums)
		for i in range(n):
			if nums[i] not in d:
				d[nums[i]] = 1
			else:
				d[nums[i]] += 1
		ans = 0
		if k == 0:
			for (i, j) in d.items():
				if j > 1:
					ans += j * (j - 1) // 2
		else:
			for (i, j) in d.items():
				if k + i in d:
					ans += d[k + i] * d[i]
		return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		c = 0
		d = dict()
		for nums in arr:
			d[nums] = 1 + d.get(nums, 0)
		for i in range(len(arr)):
			char = k + arr[i]
			if k == 0:
				c += d[char] * (d[char] - 1) / 2
				d[char] = 0
			elif char in d:
				c += d[char]
		return int(c)


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		arrdict = {}
		count = 0
		for i in arr:
			if i in arrdict:
				arrdict[i] += 1
			else:
				arrdict[i] = 1
		if k == 0:
			for i in list(arrdict.keys()):
				count += arrdict[i] * (arrdict[i] - 1) // 2
		else:
			for i in list(arrdict.keys()):
				if i - k in arrdict:
					count += arrdict[i] * arrdict[i - k]
		return count


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		m = {}
		for i in arr:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		s = 0
		for i in m:
			if i + k in m:
				if i == i + k:
					s += m[i] * (m[i] - 1) // 2
				else:
					s += m[i] * m[i + k]
		return s


from collections import Counter

class Solution:

	def countPairsWithDiffK(self, A, n, k):
		c = Counter(A)
		ans = 0
		if k == 0:
			for i in c:
				ans += c[i] * (c[i] - 1) // 2
			return ans
		for i in c:
			if i + k in c:
				ans += c[i] * c[i + k]
		return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		arr.sort()
		m = {}
		c = 0
		for i in arr:
			if i - k in m:
				c += m[i - k]
			if i not in m:
				m[i] = 1
			else:
				m[i] += 1
		return c


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = d.get(arr[i], 0) + 1
		ans = 0
		for (i, j) in d.items():
			if i - k in d and i - k != i:
				ans += d[i - k] * d.get(i, 1)
			if i - k == i:
				ans = ans + j * (j - 1) // 2
		return ans


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		c = 0
		if k == 0:
			for i in d:
				c += d[i] * (d[i] - 1) // 2
		else:
			for i in d:
				if abs(i + k) in d:
					c += d[i + k] * d[i]
		return c


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		p_c = 0
		dict = {}
		for num in arr:
			if num + k in dict:
				p_c = p_c + dict[num + k]
			if k != 0 and num - k in dict:
				p_c = p_c + dict[num - k]
			if num in dict:
				dict[num] += 1
			else:
				dict[num] = 1
		return p_c
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, k) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countPairsWithDiffK(arr, n, k)
		print(ans)
		tc -= 1


class Solution:

	def __init__(self):
		self.facts = {0: 1}

	def fact(self, n):
		if n in self.facts:
			return self.facts[n]
		else:
			self.facts[n] = n * self.fact(n - 1)
			return self.facts[n]

	def countPairsWithDiffK(self, arr, n, k):
		i = 0
		j = 1
		pairs_cnt = 0
		elems = {}
		for i in arr:
			elems[i] = elems.get(i, 0) + 1
		keys = list(sorted(elems.keys()))
		if k == 0:
			for key in elems:
				val = elems[key]
				if val > 1:
					addition = self.fact(val) // (2 * self.fact(val - 2))
					pairs_cnt += addition
			return pairs_cnt
			return sum((i for i in elems.values() if i > 1))
		for key in keys:
			required_difference_elem = key + k
			if required_difference_elem in elems:
				add_val = elems[required_difference_elem] * elems[key]
				pairs_cnt += add_val
		return pairs_cnt


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		c = 0
		d = {}
		for x in arr:
			if d.get(x + k) is not None:
				c += d[x + k]
			if k != 0 and d.get(x - k) is not None:
				c += d[x - k]
			d[x] = d.get(x, 0) + 1
		return c


from collections import Counter

class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		if k == 0:
			dict1 = Counter(arr)
			count = 0
			for i in dict1:
				if dict1[i] > 1:
					count += dict1[i] * (dict1[i] - 1) / 2
			return int(count)
		else:
			arr.sort()
			dict1 = dict()
			count = 0
			for i in arr:
				if i not in dict1:
					dict1[i] = 1
				else:
					dict1[i] += 1
				if i - k in dict1:
					count += dict1[i - k]
		return count


class Solution:

	def countPairsWithDiffK(self, arr, n, k):
		maxele = max(arr)
		hmap = [0] * (maxele + 1)
		for i in range(len(arr)):
			hmap[arr[i]] += 1
		count = 0
		for i in range(maxele + 1):
			if hmap[i]:
				if i == i + k:
					count += hmap[i] * (hmap[i] - 1) / 2
				elif i + k <= maxele:
					count += hmap[i] * hmap[i + k]
		return int(count)