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.

Sample Input:

6 10
2 8 10 5 -2 5

Sample Output:

2

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.

Approach :

Map/Dictionary Approach

1. Create a hashmap/dictionary which will store the count of occurrences of each elements and initially it will be empty.
2. 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.
3. Now increase the count of arr[i] in the hashmap/dictionary by 1.

Time Complexity : O(N)
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.