You are given an array Arr of size N. You need to find all pairs in the array that sum to a number K. If no such pair exists then output will be -1. The elements of the array are distinct and are in sorted order.
Note: (a,b) and (b,a) are considered same. Also, an element cannot pair with itself, i.e., (a,a) is invalid.
Example 1:
Input:
n = 7
arr[] = {1, 2, 3, 4, 5, 6, 7}
K = 8
Output:
3
Explanation:
We find 3 such pairs that
sum to 8 (1,7) (2,6) (3,5)
Example 2:
Input:
n = 7
arr[] = {1, 2, 3, 4, 5, 6, 7}
K = 98 
Output:
-1 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function Countpair() that takes an array (arr), sizeOfArray (n), an integer K, and return the count of the pairs which add up to the sum K. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
0 <= A_{i} <=10^{7}
2 <= N <= 10^{7}
0 <= K <= 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3


class Solution:
    def Countpair (self, arr, n, sum) : 
        #Complete the function


Solutions:
class Solution:

	def Countpair(self, arr, n, sum):
		count = 0
		front = 0
		back = n - 1
		while front < n and back >= 0:
			tempsum = arr[front] + arr[back]
			if tempsum == sum:
				count += 1
				if arr[front] == arr[back]:
					count -= 1
				front += 1
				back -= 1
			elif tempsum < sum:
				front += 1
			else:
				back -= 1
		return count // 2 if count else -1


class Solution:

	def Countpair(self, arr, n, sum):
		c = 0
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] == sum:
					c += 1
		if c == 0:
			return -1
		return c


class Solution:

	def Countpair(self, arr, n, sum):
		t = 0
		l = 0
		if n % 2 == 0:
			l = n / 2
		else:
			l = (n + 1) / 2
		(i, j) = (0, n - 1)
		while i < j:
			if arr[i] + arr[j] < sum:
				i += 1
			elif arr[i] + arr[j] > sum:
				j -= 1
			else:
				t += 1
				j -= 1
		if t == 0:
			return -1
		return t


class Solution:

	def Countpair(self, arr, n, sum):
		n = len(arr)
		pairs = set()
		count = 0
		for i in range(n):
			if sum - arr[i] in pairs:
				count += 1
			pairs.add(arr[i])
		if count == 0:
			return -1
		return count


class Solution:

	def Countpair(self, arr, n, sum):
		arr.sort()
		c = 0
		l = 0
		r = n - 1
		while l < r:
			if sum == arr[l] + arr[r]:
				c = c + 1
				l = l + 1
				r = r - 1
			elif sum > arr[l] + arr[r]:
				l = l + 1
			else:
				r = r - 1
		if c > 0:
			return c
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		res = 0
		(left, right) = (0, len(arr) - 1)
		while left < right:
			currentSum = arr[left] + arr[right]
			if currentSum < sum:
				left += 1
			elif currentSum > sum:
				right -= 1
			else:
				res += 1
				right -= 1
				left += 1
		return res if res > 0 else -1


class Solution:

	def Countpair(self, arr, n, sum):
		cnt = 0
		l = 0
		r = n - 1
		while l < r:
			k = arr[l] + arr[r]
			if k > sum:
				r -= 1
			elif k < sum:
				l += 1
			else:
				cnt += 1
				l += 1
				r -= 1
		if cnt == 0:
			return -1
		return cnt


class Solution:

	def bin_s(self, A, target):
		l = 0
		r = len(A) - 1
		while l <= r:
			mid = l + (r - l) / 2
			mid = int(mid)
			if A[mid] == target:
				return True
			elif target > A[mid]:
				l = mid + 1
			else:
				r = mid - 1
		return False

	def Countpair(self, arr, n, sum):
		l = 0
		r = n - 1
		cnt = 0
		while l < r:
			k = arr[l] + arr[r]
			if k == sum:
				cnt += 1
				l += 1
				r -= 1
			elif k > sum:
				r -= 1
			else:
				l += 1
		if cnt == 0:
			return -1
		return cnt


class Solution:

	def Countpair(self, arr, n, k):
		ans = 0
		(i, j) = (0, n - 1)
		while i < j:
			if arr[i] + arr[j] == k:
				ans += 1
				i += 1
				j -= 1
			elif arr[i] + arr[j] < k:
				i += 1
			else:
				j -= 1
		if ans == 0:
			return -1
		return ans


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = n - 1
		pairs = 0
		while i < j:
			if arr[i] + arr[j] == sum:
				pairs = pairs + 1
				i = i + 1
				j = j - 1
			elif arr[i] + arr[j] < sum:
				i = i + 1
			else:
				j = j - 1
		if pairs > 0:
			return pairs
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		ans = 0
		mp = set()
		for i in arr:
			if sum - i in mp:
				ans += 1
			mp.add(i)
		if ans == 0:
			return -1
		return ans


class Solution:

	def Countpair(self, arr, n, sum):
		d = {}
		count = 0
		pair = []
		for elem in arr:
			if sum - elem in d:
				count += 1
			else:
				d[elem] = 0
		return count if count else -1


class Solution:

	def Countpair(self, arr, n, sum):
		count = 0
		for i in range(n):
			s = arr[i]
			t = i + 1
			while t < n:
				if s + arr[t] == sum:
					count = count + 1
				if s + arr[t] > sum:
					break
				t = t + 1
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = len(arr) - 1
		l = []
		while i < j:
			if arr[i] + arr[j] == sum:
				l.append([arr[i], arr[j]])
				i = i + 1
				j = j - 1
			elif arr[i] + arr[j] > sum:
				j = j - 1
			else:
				i = i + 1
		if l:
			return len(l)
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = len(arr) - 1
		count = 0
		while i < j:
			k = arr[i] + arr[j]
			if k == sum:
				count += 1
				i += 1
				j -= 1
			elif k < sum:
				i += 1
			else:
				j -= 1
		if count >= 1:
			return count
		else:
			return -1


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = n - 1
		c = 0
		while i < j:
			if arr[j] + arr[i] == sum:
				c = c + 1
				i = i + 1
				j = j - 1
			if arr[j] + arr[i] > sum:
				j = j - 1
			if arr[j] + arr[i] < sum:
				i = i + 1
		if c == 0:
			return -1
		else:
			return c


class Solution:

	def Countpair(self, arr, n, sum):
		mp = dict()
		for i in range(n):
			if arr[i] in mp.keys():
				mp[arr[i]] += 1
			else:
				mp[arr[i]] = 1
		count = 0
		for i in arr:
			res = sum - i
			if res in mp.keys():
				mp[i] -= 1
				if mp[i] == 0:
					mp.pop(i)
				count += 1
				if res == i:
					count -= 1
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def Countpair(self, arr, n, sum):
		(left, right) = (0, n - 1)
		count = 0
		while left < right:
			if arr[left] + arr[right] == sum:
				count += 1
				left += 1
			elif arr[left] + arr[right] > sum:
				right -= 1
			else:
				left += 1
		return count if count != 0 else -1


class Solution:

	def Countpair(self, arr, n, sum):
		count = 0
		for x in range(0, n - 1):
			for y in range(x + 1, n):
				if arr[x] + arr[y] == sum:
					count += 1
		if count != 0:
			return count
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		res = []
		for i in arr:
			if i < K:
				j = K - i
				if j in arr:
					if j > i and (i, j) not in res:
						res.append((i, j))
					elif j < i and (j, i) not in res:
						res.append((j, i))
		return len(res) if res else -1


class Solution:

	def Countpair(self, arr, n, sum):
		c = 0
		for i in range(n):
			if abs(sum - arr[i]) in arr and arr[i] <= sum and (abs(sum - arr[i]) != arr[i]):
				c = c + 1
		if c == 0:
			return -1
		else:
			return c // 2


class Solution:

	def Countpair(self, arr, n, sum):
		low = 0
		c = 0
		high = n - 1
		while low < high:
			if arr[low] + arr[high] == sum:
				low = low + 1
				high = high - 1
				c = c + 1
			elif arr[low] + arr[high] < sum:
				low = low + 1
			else:
				high = high - 1
		if c == 0:
			return -1
		else:
			return c


class Solution:

	def Countpair(self, arr, n, sum):
		ar = []
		for i in arr:
			diff = sum - i
			if diff in arr and i != diff:
				arr.remove(diff)
				ar.append([i, diff])
		if len(ar) == 0:
			return -1
		else:
			return len(ar)


class Solution:

	def Countpair(self, arr, n, sum):
		pos1 = 0
		pos2 = n - 1
		count = 0
		while pos1 < pos2:
			if arr[pos1] + arr[pos2] == sum:
				count += 1
				if arr[pos1 + 1] == arr[pos1]:
					pos1 += 1
				else:
					pos2 -= 1
			elif arr[pos1] + arr[pos2] > sum:
				pos2 -= 1
			else:
				pos1 += 1
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def Countpair(self, arr, n, sum):
		dict = {}
		for i in arr:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		count = 0
		for j in dict:
			x = sum - j
			if x == j:
				if dict[j] > 1:
					count += 1
					dict[j] -= 2
			elif x in dict and (dict[j] > 0 and dict[x] > 0):
				count += 1
				dict[j] -= 1
				dict[x] -= 1
		if count:
			return count
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		cur_sum = 0
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				cur_sum = cur_sum + (arr[i] + arr[j])
				if cur_sum == sum:
					count = count + 1
				else:
					cur_sum = 0
		if count == 0:
			count = -1
		return count


from itertools import combinations

class Solution:

	def Countpair(self, arr, n, su):
		r = []
		for v in combinations(arr, 2):
			if v[0] + v[1] == su:
				r.append((arr[0], arr[1]))
		if len(r) > 0:
			return len(r)
		else:
			return -1


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = n - 1
		ans = 0
		while i < j:
			if arr[i] + arr[j] == sum:
				ans = ans + 1
				i += 1
				j -= 1
				continue
			if arr[i] + arr[j] > sum:
				j = j - 1
			else:
				i = i + 1
		return -1 if ans == 0 else ans


class Solution:

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


class Solution:

	def Countpair(self, arr, n, sum):
		s = set()
		c = 0
		for i in arr:
			if sum - i in s:
				c += 1
			s.add(i)
		if c == 0:
			return -1
		return c


class Solution:

	def Countpair(self, arr, n, sum):
		f = 0
		b = n - 1
		count = 0
		while f < b:
			req = sum - arr[f]
			if arr[b] == req:
				count += 1
				b -= 1
			elif arr[b] > req:
				b -= 1
			else:
				f += 1
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def Countpair(self, arr, n, sum):
		num1 = []
		ans = []
		s = 0
		e = n - 1
		while s < e:
			if arr[s] + arr[e] == sum:
				ans.append([arr[s], arr[e]])
				s += 1
				e -= 1
			elif arr[s] + arr[e] < sum:
				s += 1
			elif arr[s] + arr[e] > sum:
				e -= 1
		return len(ans) if ans != [] else -1


class Solution:

	def Countpair(self, arr, n, k):
		(i, j) = (0, len(arr) - 1)
		cnt = 0
		while i < j:
			s = arr[i] + arr[j]
			if s == k:
				cnt += 1
				i += 1
				j -= 1
			elif s < k:
				i += 1
			else:
				j -= 1
		if cnt:
			return cnt
		return -1


class Solution:

	def Countpair(self, arr, n, sum):
		count = 0
		for i in range(len(arr) - 1):
			tar = sum - arr[i]
			for j in range(i + 1, len(arr)):
				if arr[j] == tar:
					count += 1
		if count == 0:
			return -1
		return count


class Solution:

	def Countpair(self, arr, n, sum):
		si = 0
		ei = n - 1
		c = 0
		while si < ei:
			if arr[si] + arr[ei] == sum:
				c += 1
				si += 1
				ei -= 1
			elif arr[si] + arr[ei] < sum:
				si += 1
			else:
				ei -= 1
		if c == 0:
			return -1
		return c


class Solution:

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


class Solution:

	def Countpair(self, arr, n, sum):
		arr.sort()
		(upper, lower) = (n - 1, 0)
		counts = 0
		while upper > lower:
			if arr[upper] + arr[lower] == sum:
				counts += 1
				lower += 1
			elif arr[upper] + arr[lower] > sum:
				upper -= 1
			else:
				lower += 1
		return counts if counts != 0 else -1


class Solution:

	def Countpair(self, arr, n, sum):
		d = dict()
		c = 0
		for ele in arr:
			d[ele] = 0
		for ele in arr:
			d[ele] = d[ele] + 1
		for ele in arr:
			d[ele] = d[ele] - 1
			if sum - ele in d.keys() and d[sum - ele] > 0:
				d[sum - ele] = d[sum - ele] - 1
				c = c + 1
		if c == 0:
			return -1
		else:
			return c


class Solution:

	def Countpair(self, a, n, sum):
		c = 0
		(i, j) = (0, n - 1)
		while i < j:
			if a[i] + a[j] == sum:
				c += 1
				i += 1
				j -= 1
			elif a[i] + a[j] < sum:
				i += 1
			else:
				j -= 1
		return c if c > 0 else -1


class Solution:

	def Countpair(self, arr, n, sum):
		i = 0
		j = n - 1
		count = 0
		while i < j:
			sums = arr[i] + arr[j]
			if sums == sum:
				count += 1
				i += 1
				j -= 1
			elif sums < sum:
				i += 1
			elif sums > sum:
				j -= 1
		if not count:
			return -1
		return count


class Solution:

	def Countpair(self, arr, n, sum):
		count = 0

		def fun(arr, K):
			count = 0
			i = 0
			j = len(arr) - 1
			while i < j:
				sumi = arr[i] + arr[j]
				if sumi == K:
					i = i + 1
					j = j - 1
					count = count + 1
				if sumi < K:
					i = i + 1
				if sumi > K:
					j = j - 1
			return count
		var = fun(arr, K)
		if var == 0:
			return -1
		else:
			return var


class Solution:

	def Countpair(self, arr, n, sum):
		addit = 0
		for i in range(0, n - 1):
			for j in range(i + 1, len(arr)):
				if arr[i] + arr[j] == sum:
					addit += 1
				else:
					continue
		if addit == 0:
			return -1
		else:
			return addit


class Solution:

	def Countpair(self, numbers, n, target):
		r = len(numbers) - 1
		l = 0
		cnt = 0
		while l < r:
			if numbers[l] + numbers[r] == target:
				cnt += 1
				l += 1
				r -= 1
			elif numbers[l] + numbers[r] < target:
				l += 1
			else:
				r -= 1
		return cnt if cnt > 0 else -1


class Solution:

	def Countpair(self, arr, n, k):
		s = []
		for i in range(len(arr) - 1):
			for j in range(i, len(arr)):
				if arr[i] + arr[j] == k and arr[i] != arr[j]:
					s.append((arr[i], arr[j]))
		if len(s) >= 1:
			return len(s)
		return -1


class Solution:

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


class Solution:

	def Countpair(self, arr, n, K):
		count = 0
		i = 0
		j = 0
		while i + j + 1 < n:
			summa = arr[i] + arr[-j - 1]
			if summa == K:
				count += 1
				i += 1
				j += 1
			elif summa < K:
				i += 1
			elif summa > K:
				j += 1
		return count if count > 0 else -1