Number Of Pairs With Given Sum
Posted: 29 Jul, 2020
Difficulty: Moderate
You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.
Note:
Given array/list can contain duplicate elements.
(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.
Input format :
The first line contains 2 space-separated integers N and Sum.
The next line contains N space-separated integers representing array elements.
Output format :
Print the total number of pairs present in the array/list.
Constraints :
1 <= N <= 10^5
-10^4 <= Sum <= 10^4
-10^4 <= arr[ i ] <= 10^4
Time Limit: 1 sec
Approach 1
Approach 2
- Sort the array and take two pointers i and j, one pointer pointing to the start of the array i.e. i = 0 and another pointer pointing to the end of the array i.e. j = n – 1. If arr[i] + arr[j]
- Is greater than the Sum then decrement j.
- Lesser than the Sum then increment i.
- Equals the Sum then count such pairs.
The above three conditions will be checked while(i<j).
- To count the pairs when arr[i] + arr[j] = Sum
- Count number of elements equal to the arr[i]
- Count number of elements equal to the arr[j]
- If arr[i] and arr[j] are equal
- Then the total number of equal elements will be
the count of number of elements equal to arr[i]+count of number of elements equal to arr[j] - 1.
-1 is done because one element will get counted twice. Let’s say this count is ‘cnt’. - Now ans will be increased by (cnt * (cnt+1))/2. Because every element can pair with elements present at its right side.
- Then the total number of equal elements will be
- If not equal then ans will be increased by the product of the count of elements equal to arr[i] and the count of elements equal to arr[j].
Approach 3
- Create a hashmap/dictionary which will store the count of occurrences of each element and initially it will be empty.
- Run a loop from i=0 to N-1 and for each i’th element its value is arr[i] and we need to find the number which is equal to Sum - arr[i]. So check if sum-arr[i] is present in the hashmap/dictionary. If it is present, the answer will be increased by the count of occurrence of sum-arr[i] present in the hashmap/dictionary as arr[i] can be paired with all those sum-arr[i] elements present in its left side.
- Now increase the count of arr[i] in the hashmap/dictionary by 1.
SIMILAR PROBLEMS
Pair Product Div by K
Posted: 15 May, 2022
Difficulty: Moderate
Left Rotate an Array by One
Posted: 17 May, 2022
Difficulty: Easy
Largest Element in the Array
Posted: 17 May, 2022
Difficulty: Easy
Matrix Boundary Traversal
Posted: 20 May, 2022
Difficulty: Easy
Minimum Difference in an Array
Posted: 20 May, 2022
Difficulty: Easy