# Given an array, count the number of pairs with a given sum.

Objective: Given an array of integers, write a program to count all the pairs with the given sum.

Example:

```Given array: [1, 5, 7, 1, -1], Sum= 6
Total Pairs: 3
Note: pairs are (1, 5), (5, 1) and (7, -1)

Given array: [4, 5, 1, 2, 9, -2, -4], Sum= 5
Total Pairs: 2
Note: pairs are (4, 1) and (9, -4)

Given array: [3, 3, 3, 3], Sum= 6
Total Pairs: 6
```

Approach:

Naive approach to run the nested loops and add each pair to check it with the given sum.

Time Complexity: O(N2)

Better approach is to use the Map.

1. Traverse the array and construct a map with elements in the array as key and their count as value.
2. Initialize pairCount = 0.
3. Now traverse the map and for each key X in map with count>0
• Do Y = sum –  X, check if Y is present in map and count>0 , if yes then get the X and Y counts from map.
•  Let’s say X_COUNT is count of X and Y_COUNT is count of Y.
• If X and Y are same means both elements are same then do pairCount + X_COUNT*(X_COUNT-1)/2. (Number of ways to pick 2 elements out of n = nC2)
• If X and Y are not same then Do pairCount = pairCount + X_COUNT*Y_COUNT.
• Put X and Y count 0 in the map.
4. Return pairCount.

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

Complete Code

Output:

```Given array: [1, 5, 7, 1, -1], Sum= 6
Total Pairs: 3
```