Given an array of N integers, and an integer K, find the number of pairs of elements in the array whose sum is equal to K.
Example 1:
Input:
N = 4, K = 6
arr[] = {1, 5, 7, 1}
Output: 2
Explanation: 
arr[0] + arr[1] = 1 + 5 = 6 
and arr[1] + arr[3] = 5 + 1 = 6.
Example 2:
Input:
N = 4, K = 2
arr[] = {1, 1, 1, 1}
Output: 6
Explanation: 
Each 1 will produce sum 2 with any 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getPairsCount() which takes arr[], n and k as input parameters and returns the number of pairs that have sum K.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= K <= 10^{8}
1 <= Arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

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

        # code here

Solutions:
import math
from collections import Counter

class Solution:

	def getPairsCount(self, arr, n, k):
		mpp = Counter(arr)
		c = 0
		flag = False
		a = list(set(arr))
		for i in range(len(a)):
			x = k - a[i]
			if x in mpp:
				if k - a[i] == a[i]:
					n = mpp[a[i]]
					c += n * (n - 1) // 2
				else:
					c += mpp[a[i]] * mpp[k - a[i]]
					flag = True
		if flag == True:
			return (c + 1) // 2
		return c


class Solution:

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


class Solution:

	def getPairsCount(self, a, n, k):
		mydict = dict()
		c = 0
		for i in range(0, n):
			temp = k - a[i]
			if temp in mydict:
				val = mydict[temp]
				for j in range(0, val):
					c += 1
			if a[i] not in mydict:
				mydict[a[i]] = 1
			else:
				mydict[a[i]] += 1
		return c


class Solution:

	def getPairsCount(self, arr, n, sum):
		unordered_map = {}
		count = 0
		for i in range(n):
			if sum - arr[i] in unordered_map:
				count += unordered_map[sum - arr[i]]
			if arr[i] in unordered_map:
				unordered_map[arr[i]] += 1
			else:
				unordered_map[arr[i]] = 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		from collections import defaultdict
		dct = defaultdict(int)
		count = 0
		for num in arr:
			count += dct[k - num]
			dct[num] += 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		from collections import Counter
		dct = Counter(arr)
		count = 0
		for num in dct:
			if k - num in dct:
				val = k - num
				if val != num:
					count += dct[num] * dct[val]
					dct[num] = 0
				else:
					repeats = dct[num]
					count += repeats * (repeats - 1) // 2
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		hashM = {}
		ans = 0
		for i in range(n):
			t = k - arr[i]
			if t in hashM:
				ans += hashM[t]
			if arr[i] not in hashM:
				hashM[arr[i]] = 0
			hashM[arr[i]] += 1
		return ans


from collections import Counter

class Solution:

	def getPairsCount(self, arr, n, k):
		hm = Counter(arr)
		count = 0
		for n in arr:
			hm[n] -= 1
			if k - n in hm:
				count += hm[k - n]
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		cnt = 0
		d = {}
		for i in range(n):
			if k - arr[i] in d:
				cnt += d[k - arr[i]]
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		return cnt


class Solution:

	def getPairsCount(self, arr, n, k):
		dic = dict()
		count = 0
		for i in range(n):
			data = k - arr[i]
			if data in dic:
				count = count + dic[k - arr[i]]
			dic[arr[i]] = dic.get(arr[i], 0) + 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		a = {}
		cnt = 0
		for i in arr:
			b = k - i
			if b in a:
				cnt = cnt + a[b]
			if i in a:
				a[i] = a[i] + 1
			else:
				a[i] = 1
		return cnt


class Solution:

	def getPairsCount(self, arr, n, k):
		freq_map = {}
		count = 0
		for num in arr:
			target = k - num
			if target in freq_map:
				count += freq_map[target]
			freq_map[num] = freq_map.get(num, 0) + 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		(s, d) = (0, {})
		for elem in arr:
			d.update({elem: d.get(elem, 0) + 1})
		for elem in d:
			if elem * 2 == k:
				s += d[elem] * (d[elem] - 1) // 2
				d[elem] = 0
			elif d[elem] and d.get(k - elem, 0):
				s += d[elem] * d.get(k - elem, 0)
				d[elem] = 0
		return s


class Solution:

	def getPairsCount(self, arr, n, k):
		arr.sort()
		mx = max(arr)
		freq = [0] * (mx + 1)
		for elem in arr:
			freq[elem] += 1
		d = {}
		for elem in arr:
			d.update({elem: d.get(elem, 0) + 1})
		s = 0
		s = 0
		for elem in d:
			if elem * 2 == k:
				s += d[elem] * (d[elem] - 1) // 2
				d[elem] = 0
			elif d[elem] and d.get(k - elem, 0):
				s += d[elem] * d.get(k - elem, 0)
				d[elem] = 0
		return s


class Solution:

	def getPairsCount(self, arr, n, k):
		d = dict()
		c = 0
		for i in arr:
			A = k - i
			if A in d:
				c = c + d[A]
			if i in d:
				d[i] = d[i] + 1
			else:
				d[i] = 1
		return c


class Solution:

	def getPairsCount(self, arr, n, sum):
		m = dict()
		for i in range(n):
			if arr[i] in m.keys():
				m[arr[i]] += 1
			else:
				m[arr[i]] = 1
		twice_count = 0
		for i in range(0, n):
			if sum - arr[i] in m.keys():
				twice_count += m[sum - arr[i]]
			if sum - arr[i] == arr[i]:
				twice_count -= 1
		return int(twice_count / 2)


class Solution:

	def getPairsCount(self, arr, n, k):
		count = 0
		hash = {}
		for i in range(n):
			if k - arr[i] in hash:
				count += hash[k - arr[i]]
			if arr[i] in hash:
				hash[arr[i]] += 1
			else:
				hash[arr[i]] = 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		ct = 0
		freq = {}
		for i in range(0, n):
			if k - arr[i] in freq:
				ct += freq[k - arr[i]]
			freq[arr[i]] = 1 + freq.get(arr[i], 0)
		return ct


class Solution:

	def getPairsCount(self, arr, n, k):
		hashmap = {}
		for i in arr:
			hashmap[i] = hashmap.get(i, 0) + 1
		count = 0
		for i in arr:
			b = k - i
			a = i
			if b in hashmap:
				count += hashmap[b]
			if b == a:
				count -= 1
		return count // 2


from collections import defaultdict

class Solution:

	def getPairsCount(self, arr, n, k):
		d = defaultdict(int)
		ans = 0
		for a in arr:
			ans += d[k - a]
			d[a] += 1
		return ans


class Solution:

	def getPairsCount(self, arr, n, k):
		from collections import Counter
		m = Counter()
		ans = 0
		for i in arr:
			if m[k - i]:
				ans += m[k - i]
			m[i] += 1
		return ans


class Solution:

	def getPairsCount(self, arr, n, k):
		dict1 = {}
		c = 0
		for i in range(n):
			target = k - arr[i]
			if target in dict1:
				c += dict1[target]
			if arr[i] in dict1:
				dict1[arr[i]] += 1
			else:
				dict1[arr[i]] = 1
		return c


class Solution:

	def getPairsCount(self, arr, n, k):
		pair_count = 0
		compliment_count_map = {}
		for num in arr:
			compliment = k - num
			if compliment in compliment_count_map:
				pair_count += compliment_count_map[compliment]
			if num in compliment_count_map:
				compliment_count_map[num] = compliment_count_map[num] + 1
			else:
				compliment_count_map[num] = 1
		return pair_count


class Solution:

	def getPairsCount(self, arr, n, k):
		index = dict()
		pair = 0
		for i in range(n):
			if k > arr[i]:
				c = k - arr[i]
				if index.get(c) != None:
					pair = pair + index.get(c)
				index[arr[i]] = index.get(arr[i], 0) + 1
		return pair


from collections import Counter

class Solution:

	def getPairsCount(self, arr, n, k):
		c = Counter(arr)
		ans = 0
		for num in arr:
			if k - num in c:
				ans += c[k - num]
			if k - num == num:
				ans -= 1
		return int(ans / 2)


class Solution:

	def getPairsCount(self, arr, n, k):
		count = 0
		data = {}
		for i in arr:
			stored_data = data.get(k - i, 0)
			count += stored_data
			data[i] = data.get(i, 0) + 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		hashm = {}
		cnt = 0
		for i in range(len(arr)):
			if arr[i] not in hashm:
				hashm[arr[i]] = 1
			else:
				hashm[arr[i]] += 1
		for i in range(len(arr)):
			elem = k - arr[i]
			if elem in hashm:
				cnt += hashm[elem]
			if elem == arr[i]:
				cnt -= 1
		return cnt // 2


class Solution:

	def getPairsCount(self, arr, n, k):
		freq = {}
		pairs = 0
		for num in arr:
			if num in freq:
				freq[num] += 1
			else:
				freq[num] = 1
		for num in arr:
			complement = k - num
			if complement in freq:
				pairs += freq[complement]
			if num == complement:
				pairs -= 1
		return pairs // 2


class Solution:

	def getPairsCount(self, arr, n, k):
		hashmap = {}
		pairs = 0
		for val in arr:
			if val in hashmap:
				hashmap[val] += 1
			else:
				hashmap[val] = 1
		for val in arr:
			if k - val in hashmap:
				pairs += hashmap[k - val]
				if val == k - val:
					pairs -= 1
		return int(pairs / 2)


class Solution:

	def getPairsCount(self, arr, n, k):
		dist = {}
		pairs = 0
		for i in arr:
			if k - i in dist:
				pairs += dist[k - i]
			if i in dist:
				dist[i] += 1
			else:
				dist[i] = 1
		return pairs


class Solution:

	def getPairsCount(self, arr, n, k):
		freq = dict()
		used_numbers = dict()
		ans = 0
		for i in range(0, n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
		for i in range(0, n):
			if arr[i] not in used_numbers:
				pair_two = k - arr[i]
				if pair_two == arr[i]:
					ans += freq[arr[i]] * (freq[arr[i]] - 1) // 2
					used_numbers[arr[i]] = 1
					continue
				if pair_two in freq:
					ans += freq[arr[i]] * freq[pair_two]
					used_numbers[pair_two] = 1
				used_numbers[arr[i]] = 1
		return ans


class Solution:

	def getPairsCount(self, arr, n, k):
		dic_val = dict()
		pair = 0
		for i in range(len(arr)):
			if arr[i] >= k:
				continue
			pp = k - arr[i]
			if pp in dic_val:
				pair = pair + dic_val[pp]
				if arr[i] in dic_val:
					dic_val[arr[i]] = 1 + dic_val[arr[i]]
				else:
					dic_val[arr[i]] = 1
			elif arr[i] in dic_val:
				dic_val[arr[i]] = 1 + dic_val[arr[i]]
			else:
				dic_val[arr[i]] = 1
		return pair


class Solution:

	def getPairsCount(self, arr, n, k):
		(dict, ans) = ({}, 0)
		for el in arr:
			if k - el in dict:
				ans += dict[k - el]
			if not el in dict:
				dict[el] = 1
			else:
				dict[el] += 1
		return ans


import sys

class Solution:

	def getPairsCount(self, arr, n, k):
		a = {}
		sum = 0
		for i in range(len(arr)):
			if arr[i] not in a:
				a[arr[i]] = 0
			a[arr[i]] += 1
		for i in range(len(arr)):
			if k - arr[i] in a:
				sum = sum + a[k - arr[i]]
				if k - arr[i] == arr[i]:
					sum -= 1
		return int(sum / 2)


class Solution:

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


class Solution:

	def getPairsCount(self, arr, n, k):
		dict = {}
		pairs = 0
		arr = sorted(arr)
		for val in arr:
			if val in dict:
				dict[val] += 1
			else:
				dict[val] = 1
		for i in range(n):
			if k - arr[i] in dict:
				pairs += dict[k - arr[i]]
			if k - arr[i] == arr[i]:
				pairs -= 1
		return int(pairs / 2)


class Solution:

	def getPairsCount(self, arr, n, k):
		d = {}
		count = 0
		for (i, e) in enumerate(arr):
			if k - e in d:
				count += d[k - e]
			if e in d:
				d[e] += 1
			else:
				d[e] = 1
		return count


class Solution:

	def getPairsCount(self, arr, n, t):
		dic = {}
		for i in range(len(arr)):
			dic[arr[i]] = dic.get(arr[i], 0) + 1
		count = 0
		for (k, v) in dic.items():
			if t - k in dic:
				if k != t - k:
					count += v * dic[t - k]
				else:
					count += v * (v - 1)
		return count // 2


from collections import defaultdict

class Solution:

	def getPairsCount(self, arr, n, k):
		visited = defaultdict(int)
		count = 0
		for x in arr:
			try:
				count += visited[k - x]
			except:
				pass
			visited[x] += 1
		return count


class Solution:

	def getPairsCount(self, arr, n, k):
		mp = dict()
		c = 0
		for i in range(n):
			target = k - arr[i]
			if target in mp:
				c = c + mp[k - arr[i]]
			mp[arr[i]] = mp.get(arr[i], 0) + 1
		return c


class Solution:

	def getPairsCount(self, arr, n, k):
		c = 0
		d = {}
		for a in arr:
			if k - a in d:
				c += d[k - a]
			if a in d:
				d[a] += 1
			else:
				d[a] = 1
		return c


class Solution:

	def getPairsCount(self, arr, n, k):
		c = 0
		d = {}
		for (i, a) in enumerate(arr):
			if a in d:
				d[a].append(i)
			else:
				d[a] = [i]
		for (i, a) in enumerate(arr):
			if k - a in d:
				for j in d[k - a]:
					if j > i:
						c += 1
		return c


class Solution:

	def getPairsCount(self, arr, n, k):
		x = {}
		ans = 0
		for i in arr:
			num = k - i
			if num in x:
				ans += x[num]
			try:
				x[i] += 1
			except:
				x[i] = 1
		return ans


from collections import defaultdict

class Solution:

	def getPairsCount(self, arr, n, k):
		val_map = defaultdict(int)
		cnt = 0
		for num in arr:
			if val_map.get(k - num):
				cnt += val_map[k - num]
			val_map[num] += 1
		return cnt


class Solution:

	def getPairsCount(self, arr, n, k):
		arr.sort()
		result = []
		i = 0
		j = n - 1
		while i < j:
			if arr[i] + arr[j] < k:
				i += 1
			elif arr[i] + arr[j] > k:
				j -= 1
			elif arr[i] != arr[j]:
				c1 = 0
				temp1 = arr[i]
				while arr[i] == temp1:
					i += 1
					c1 += 1
				c2 = 0
				temp2 = arr[j]
				while arr[j] == temp2:
					j -= 1
					c2 += 1
				for _ in range(0, c1 * c2):
					result.append((temp1, temp2))
			else:
				c3 = 0
				while arr[j] == arr[i]:
					j -= 1
					c3 += 1
				for _ in range(0, c3 * (c3 - 1) // 2):
					result.append((arr[i], arr[i]))
		return len(result)


class Solution:

	def getPairsCount(self, arr, n, k):
		freq_map = {}
		for i in range(n):
			if arr[i] not in freq_map.keys():
				freq_map[arr[i]] = 1
			else:
				freq_map[arr[i]] += 1
		count = 0
		for i in range(n):
			diff = k - arr[i]
			if diff in freq_map.keys():
				count = count + freq_map[diff]
				if diff == arr[i]:
					count -= 1
		count = count // 2
		return count


class Solution:

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


class Solution:

	def getPairsCount(self, arr, n, k):
		s = dict()
		cnt = 0
		for i in range(n):
			temp = k - arr[i]
			if temp in s:
				cnt += s[temp]
			if arr[i] in s:
				s[arr[i]] += 1
			else:
				s[arr[i]] = 1
		return cnt


from collections import defaultdict

class Solution:

	def getPairsCount(self, arr, n, k):
		(seen, count) = ({}, 0)
		for i in range(n):
			if k - arr[i] in seen:
				count += seen[k - arr[i]]
			seen[arr[i]] = seen.get(arr[i], 0) + 1
		return count

		def sum(i, arr, t):
			if t == 0:
				return 1
			if i == 0:
				if arr[0] == t:
					return 1
				return 0
			x = sum(i - 1, arr, t)
			y = 0
			if arr[i] <= t:
				y = sum(i - 1, arr, t - arr[i])
			return x + y
		return sum(n - 1, arr, k)


class Solution:

	def getPairsCount(self, arr, n, k):
		m = {}
		ans = 0
		for i in range(n):
			if k - arr[i] in m:
				ans += m[k - arr[i]]
			m[arr[i]] = m.get(arr[i], 0) + 1
		return ans


class Solution:

	def getPairsCount(self, arr, n, k):
		freq_dict = {}
		pair_count = 0
		for i in range(n):
			if k - arr[i] in freq_dict:
				pair_count += freq_dict[k - arr[i]]
			if arr[i] in freq_dict:
				freq_dict[arr[i]] += 1
			else:
				freq_dict[arr[i]] = 1
		return pair_count