Number of Pairs with Given Sum — Asked in Amazon, Samsung and Nagarro Interview
Problem Statement :
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’.
The first line contains 2 space-separated integers N and Sum.
Next line contains N space-separated integers representing array elements.
2 8 10 5 -2 5
Explanation of Sample Test Case:
We have 2 pairs that sum up to 10. They are, (2, 8) and (5, 5). Note that we are not counting (8,2), as (2,8) and (8,2) is considered same.
- Create a hashmap/dictionary which will store the count of occurrences of each elements 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.
Time Complexity : O(N)
Space Complexity : O(N)