# 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(N^{2})

Better approach is to use the Map.

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

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