This post is completed by 1 user

Add to List 
473. 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 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_COUNT1)/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.
 Return pairCount.
Time Complexity: O(N), Space Complexity: O(N)
Output:
Given array: [1, 5, 7, 1, 1], Sum= 6 Total Pairs: 3