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

- Is greater than the
- 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.