Number Of Pairs With Given Sum

PROBLEM STATEMENT

Given array/list can contain duplicate elements.

(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.

The first line contains 2 space-separated integers N and Sum.

The next line contains N space-separated integers representing array elements.

Print the total number of pairs present in the array/list.

1 <= N <= 10^5
-10^4 <= Sum <= 10^4
-10^4 <=  arr[ i ] <= 10^4

Time Limit: 1 sec

Approach 1

Initialize the ans = 0
Run two loops first from i = 0 to n-1 and second from j = i+1 to n-1 and if arr[i] + arr[j] == Sum then increase the ans by 1.
Return ans

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