Given two sorted arrays(arr1[] and arr2[]) of size M and N of distinct elements. Given a value Sum. The problem is to count all pairs from both arrays whose sum is equal to Sum.
Note: The pair has an element from each array.
Example 1:
Input:
M=4, N=4 , Sum = 10
arr1[] = {1, 3, 5, 7}
arr2[] = {2, 3, 5, 8} 
Output: 2
Explanation: The pairs are: (5, 5) and (7, 3).  
 
Example 2:
Input:
N=4, M=4, sum=5 
arr1[] = {1, 2, 3, 4}
arr2[] = {5, 6, 7, 8}
Output: 0
 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countPairs() that takes array arr1, array arr2, integer M, integer N and integer x as parameters and return the count of all pairs from both arrays whose sum is equal to x.
 
Expected Time Complexity: O(M+N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ M, N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def countPairs(self,arr1, arr2, M, N, x):
        #code here.


Solutions:
class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		i = 0
		j = N - 1
		while i < M and j >= 0:
			pairsum = arr1[i] + arr2[j]
			if x == pairsum:
				count += 1
				i += 1
				j -= 1
			elif pairsum < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		num = 0
		s1 = set(arr2)
		for i in arr1:
			if x - i in s1:
				num += 1
		return num


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		s_arr2 = set(arr2)
		for i in arr1:
			if x - i in s_arr2:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		c = 0
		s = set(arr2)
		for i in range(M):
			if x - arr1[i] in s:
				c = c + 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		c = 0
		for i in range(M):
			if arr1[i] > x:
				pass
			for j in range(N):
				if arr2[j] > x:
					break
				if arr1[i] + arr2[j] == x:
					c = c + 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, m, n, x):
		pair = 0
		(i, j) = (0, n - 1)
		while i < m and j != -1:
			if arr1[i] + arr2[j] > x:
				j -= 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			elif arr1[i] + arr2[j] == x:
				i += 1
				j -= 1
				pair += 1
		return pair


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		rec = Counter(arr2)
		cnt = 0
		for val in arr1:
			if x - val in rec:
				cnt += rec[x - val]
		return cnt
from collections import Counter


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		d1 = {}
		d2 = {}
		count = 0
		for i in arr2:
			if i in d2:
				d2[i] += 1
			else:
				d2[i] = 1
		for i in arr1:
			j = x - i
			if j in d2:
				count += d2[j]
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		d1 = {}
		c = 0
		for i in range(M):
			if arr1[i] in d1:
				d1[arr1[i]] = d1[arr1[i]] + 1
			else:
				d1[arr1[i]] = 1
		for i in range(N):
			a = x - arr2[i]
			if a in d1:
				c = c + d1[a]
		return c


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		cou = 0
		arr3 = set(arr2)
		for i in arr1:
			if x - i in arr3:
				cou += 1
		return cou


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		pair = 0
		(i, j) = (0, N - 1)
		while i < M and j != -1:
			if arr1[i] + arr2[j] > x:
				j -= 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			elif arr1[i] + arr2[j] == x:
				i += 1
				j -= 1
				pair += 1
		return pair


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		first = 0
		second = N - 1
		sm = arr1[first] + arr2[second]
		if sm == x:
			return 1
		count = 0
		while first < M and second >= 0:
			sm = arr1[first] + arr2[second]
			if sm < x:
				first += 1
			elif sm > x:
				second -= 1
			else:
				count += 1
				first += 1
				second -= 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		cou = 0
		mp = {}
		for i in arr2:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		for j in arr1:
			rem = x - j
			if rem in mp:
				cou += 1
		return cou


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		left = 0
		right = N - 1
		while left < M and right != -1:
			if arr1[left] + arr2[right] == x:
				count += 1
				right -= 1
				left += 1
			elif arr1[left] + arr2[right] > x:
				right -= 1
			else:
				left += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		hashmap = {}
		while arr2:
			hashmap[arr2[0]] = 1
			del arr2[0]
		for item in arr1:
			if x - item in hashmap:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		s = set()
		for i in range(M):
			s.add(arr1[i])
		for j in range(N):
			if x - arr2[j] in s:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		op = 0
		l = 0
		r = N - 1
		while l < m and r >= 0:
			if arr1[l] + arr2[r] == x:
				l = l + 1
				r = r - 1
				op = op + 1
			elif arr1[l] + arr2[r] < x:
				l = l + 1
			else:
				r = r - 1
		return op


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		m = 0
		n = N - 1
		while m < M and n >= 0:
			if arr1[m] + arr2[n] == x:
				count += 1
				m += 1
				n -= 1
			elif arr1[m] + arr2[n] < x:
				m += 1
			else:
				n -= 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		convert_set = set()
		for i in range(m):
			convert_set.add(arr1[i])
		for j in range(n):
			if x - arr2[j] in convert_set:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		(cnt, sarr2) = (0, set(arr2))
		for i in arr1:
			if x - i in sarr2:
				cnt += 1
		return cnt


class Solution:

	def countPairs(self, arr1, arr2, m, n, Sum):
		count = 0
		(i, j) = (0, n - 1)
		while i < m and j >= 0:
			if arr1[i] + arr2[j] == Sum:
				count += 1
				i += 1
				j -= 1
			elif arr1[i] + arr2[j] > Sum:
				j -= 1
			else:
				i += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		c = 0
		arr2_dict = {num: True for num in arr2}
		for i in arr1:
			if x - i in arr2_dict:
				c += 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		for i in range(0, M):
			if arr1[i] < x and x - arr1[i] in arr2:
				count += 1
			else:
				continue
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		i = 0
		j = len(arr2) - 1
		c = 0
		while i < len(arr1) and j >= 0:
			if arr1[i] + arr2[j] == x:
				c = c + 1
				i = i + 1
			elif arr1[i] + arr2[j] > x:
				j = j - 1
			else:
				i = i + 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, m, n, x):
		cnt = 0
		d1 = {}
		for i in range(m):
			d1[x - arr1[i]] = arr1[i]
		for i in range(n):
			if arr2[i] in d1:
				cnt += 1
		return cnt


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		setti = set(arr1)
		return sum([x - item in setti for item in arr2])


class Solution:

	def countPairs(self, a1, a2, m, N, s):
		i = 0
		j = len(a2) - 1
		c = 0
		while i < m and j >= 0:
			if a1[i] + a2[j] > s:
				j -= 1
			elif a1[i] + a2[j] < s:
				i += 1
			else:
				c += 1
				i += 1
				j -= 1
		return c


class Solution:

	def bin_sea(self, arr, t):
		low = 0
		high = len(arr) - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] < t:
				low = mid + 1
			elif arr[mid] > t:
				high = mid - 1
			else:
				return True
		return False

	def countPairs(self, arr1, arr2, M, N, x):
		c = 0
		for i in range(M):
			op = x - arr1[i]
			if self.bin_sea(arr2, op):
				c += 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		dic1 = {}
		for i in arr1:
			a = x - i
			dic1[a] = i
		c = 0
		for i in arr2:
			if i in dic1:
				c += 1
		return c


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		d = {}
		for i in arr1:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		k = 0
		for i in arr2:
			c = x - i
			if d.get(c) != None:
				k = k + d[c]
		return k


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		numbers = set(arr1)
		for element in arr2:
			if x - element in numbers:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		H = {}
		for i in range(M):
			H[arr1[i]] = 1
		for j in range(N):
			if x - arr2[j] in H.keys():
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, m, n, x):
		ptr1 = -1
		ptr2 = 0
		count = 0
		while ptr1 >= -m and ptr2 <= n - 1:
			if arr1[ptr1] + arr2[ptr2] == x:
				count += 1
				ptr1 -= 1
				ptr2 += 1
			elif arr1[ptr1] + arr2[ptr2] < x:
				ptr2 += 1
			else:
				ptr1 -= 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		total_count = 0
		for i in arr1:
			if i <= x and x - i <= arr2[N - 1]:
				total_count = total_count + arr2.count(x - i)
		return total_count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		from collections import Counter
		d = Counter(arr2)
		count = 0
		for i in arr1:
			if x - i in d:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		set1 = set(arr1)
		set2 = set(arr2)
		count = 0
		for i in arr1:
			if x - i in set2:
				count += 1
				set1.discard(i)
		for i in arr2:
			if x - i in set1:
				count += 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		table1 = {}
		table2 = {}
		for (i, v) in enumerate(arr1):
			table1[v] = i
		for (i, v) in enumerate(arr2):
			table2[v] = i
		count = 0
		for i in arr1:
			c = x - i
			try:
				table2[c]
				count += 1
				table1.pop(i)
			except:
				continue
		for i in arr2:
			c = x - i
			try:
				table1[c]
				count += 1
			except:
				continue
		return count


class Solution:

	def countPairs(self, arr1, arr2, m, n, x):
		count = 0
		l = 0
		r = n - 1
		while l < m and r >= 0:
			if arr1[l] + arr2[r] == x:
				l += 1
				r -= 1
				count += 1
			elif arr1[l] + arr2[r] < x:
				l += 1
			else:
				r -= 1
		return count


class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		set1 = set(arr1)
		count = 0
		for item in arr2:
			count += x - item in set1
		return count


def ispresent(arr2, low, high, value):
	while low <= high:
		mid = (low + high) // 2
		if arr2[mid] == value:
			return True
		elif arr2[mid] > value:
			high = mid - 1
		else:
			low = mid + 1
	return False

class Solution:

	def countPairs(self, arr1, arr2, M, N, x):
		count = 0
		for i in arr1:
			if ispresent(arr2, 0, N - 1, x - i):
				count += 1
		return count