This post is completed by 3 users

  • 0
 Add to List
Medium

517. Count number of pairs in an array with sum = K

Given an array of integers and number K, write a program to find the number of pairs which has sum equal to K.

Example:

int input [] = {6, 3, 2, 9, 2, 2, 2, 1}
int K = 4
Output: 7

int input [] = {5, 5, 5, 5}
int K = 10
Output: 6

int input [] = {1, 2, 3, 4}
int K = 5
Output: 2

Naive Approach:

Use nested loops and compare each element with all other elements and check if the difference to elements is K, if yes then count it. 

Time Complexity: O(N2)

Better Solution: Sorting.

  1. Sort the array input[] in ascending order.
  2. Initialize pairs = 0.
  3. Have two pointers, let's call these i and j.  i at index 0 and j at index input.length-1.
  4. Check 
    1. If input[i] + input[j] > K then do j--.
    2. If input[i] + input[j] < K then do i++.
    3. If input[i] + input[j] = K, then count all the occurrences of input[i] (say x) and input[j] (say y), then pairs += x*y. If input[i] and input[j] are same then n = x + y and  pairs += n*(n+1)/2.  

Time Complexity: O(nlogn)

Output

Number of pairs with sum = 4 is/are: 7

Related Problems: