Given an array of integers, and a number ‘sum’, find the number of pairs of integers in the array whose sum is equal to ‘sum’.
Examples:
Input : arr[] = {1, 5, 7, -1},
sum = 6
Output : 2
Pairs with sum 6 are (1, 5) and (7, -1)
Input : arr[] = {1, 5, 7, -1, 5},
sum = 6
Output : 3
Pairs with sum 6 are (1, 5), (7, -1) &
(1, 5)
Input : arr[] = {1, 1, 1, 1},
sum = 2
Output : 6
There are 3! pairs with sum 2.
Input : arr[] = {10, 12, 10, 15, -1, 7, 6,
5, 4, 2, 1, 1, 1},
sum = 11
Output : 9
Expected time complexity O(n)
Naive Solution – A simple solution is to traverse each element and check if there’s another number in the array which can be added to it to give sum.
Python3
# Python3 implementation of simple method# to find count of pairs with given sum.# Returns number of pairs in arr[0..n-1]# with sum equal to 'sum'def getPairsCount(arr, n, sum): count = 0 # Initialize result # Consider all possible pairs # and check their sums for i in range(0, n): for j in range(i + 1, n): if arr[i] + arr[j] == sum: count += 1 return count# Driver functionarr = [1, 5, 7, -1, 5]n = len(arr)sum = 6print("Count of pairs is", getPairsCount(arr, n, sum))# This code is contributed by Smitha Dinesh Semwal |
Output
Count of pairs is 3
Time Complexity: O(n2)
Auxiliary Space: O(1)
Efficient solution –
A better solution is possible in O(n) time. Below is the Algorithm –
- Create a map to store frequency of each number in the array. (Single traversal is required)
- In the next traversal, for every element check if it can be combined with any other element (other than itself!) to give the desired sum. Increment the counter accordingly.
- After completion of second traversal, we’d have twice the required value stored in counter because every pair is counted two times. Hence divide count by 2 and return.
Below is the implementation of above idea :
Python3
# Python 3 implementation of simple method# to find count of pairs with given sum.import sys# Returns number of pairs in arr[0..n-1]# with sum equal to 'sum'def getPairsCount(arr, n, sum): m = [0] * 1000 # Store counts of all elements in map m for i in range(0, n): m[arr[i]] += 1 twice_count = 0 # Iterate through each element and increment # the count (Notice that every pair is # counted twice) for i in range(0, n): twice_count += m[sum - arr[i]] # if (arr[i], arr[i]) pair satisfies the # condition, then we need to ensure that # the count is decreased by one such # that the (arr[i], arr[i]) pair is not # considered if (sum - arr[i] == arr[i]): twice_count -= 1 # return the half of twice_count return int(twice_count / 2)# Driver functionarr = [1, 5, 7, -1, 5]n = len(arr)sum = 6print("Count of pairs is", getPairsCount(arr, n, sum))# This code is contributed by# Smitha Dinesh Semwal |
Output
Count of pairs is 3
Time Complexity: O(n)
Auxiliary Space: O(n)
The extra space is used to store the elements in the map.
Please refer complete article on Count pairs with given sum for more details!
