This post is completed by 1 user

  • 0
 Add to List
Beginner

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(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)

Output:

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

Related Problems: