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