Problem Statement:
Geeks For Geeks : https://www.geeksforgeeks.org/problems/pair-with-given-sum-in-a-sorted-array4940/1
You are given an integer target and an array arr[]. You have to find number of pairs in arr[] which sums up to target. It is given that the elements of the arr[] are in sorted order.
Note: pairs should have elements of distinct indexes.
Input: arr[] = [-1, 1, 5, 5, 7], target = 6
Output: 3
Explanation: There are 3 pairs which sum up to 6 : {1, 5}, {1, 5} and {-1, 7}.
Input: arr[] = [1, 1, 1, 1], target = 2
Output: 6
Explanation: There are 6 pairs which sum up to 2 : {1, 1}, {1, 1}, {1, 1}, {1, 1}, {1, 1} and {1, 1}.
Input: arr[] = [-1, 10, 10, 12, 15], target = 125 Output: 0 Explanation: There is no such pair which sums up to 4.
My Approach
- Store the occurence
- Iterate and update count.
class Solution:
def countPairs (self, arr, target) :
#Complete the function
n = len(arr)
hash_set = {}
count = 0
for itr in range(n):
if hash_set.get(arr[itr]) is None:
hash_set[arr[itr]] = [itr]
else:
hash_set[arr[itr]].append(itr)
for itr in range(n):
rem = target - arr[itr]
for index in hash_set.get(rem, []):
if index > itr:
count += 1
return count