POTD #18 - Pair with given sum in a sorted array | Geeks For Geeks

{% raw %}

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 = 6Output: 3Explanation: There are 3 pairs which sum up to 6 : {1, 5}, {1, 5} and {-1, 7}.

Input: arr[] = [1, 1, 1, 1], target = 2Output: 6Explanation: 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 = 125Output: 0Explanation: 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

{% endraw %}