# 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**

- 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)