Count pair with Given Sum

Difficulty Level Easy
Frequently asked in Accolite Amazon Factset Hike
Array Hashing Math SortingViews 2938

In problem “count pair with given sum” we have given an integer array[] and another number say ‘sum’, you have to determine whether any of the two elements in a given array has a sum equal to “sum”.

Example

Input:

arr []={1,3,4,6,7} and sum = 9.

Output:

“ Elements found with the given sum” as there are ‘3’ and ‘6’ which has sum equal to ‘9’.

Input:

arr []={11,3,5,7,10} and sum = 20.

Output:

“Elements not found with the given sum” as there are not any number which has sum equal to ‘8’.

Algorithm

  1. Declare a set.
  2. While 0 to ‘i’ is less than the length of the array.
    1. Set j to sum-arr[i].
    2. Check if the set contains ‘j’, if true then print the j and arr[i], this will be the pair.
    3. Else add the arr[i] into the set.

Explanation

We have given a problem statement, in which we are given with integers array and a number say ‘sum’. Our task is to determine whether an array has any of the two elements that have a summation equal to a given “sum”.

Our main idea is to use HashSet and to find a pair. For which we are going to store the difference of sum and each value of array while traversing, because a pair has those two elements and a given sum is the key to find another element, that’s why we storing all of the array elements into the set and look into it if one of the elements in pair is either present or not.

To find it out, we will use a hashing method.

Let us take an example:

arr[] = { 1, 4, 45, 6, 10, 8 };

  • i=0, myset, sum=16;

j=sum-arr[i];

that is j=16-1=15 and surely ‘j’ will not be present in a map.

So it add arr[i] that is ‘1’ into myset.

  • i=1, myset={1}, sum=16;

j=sum-arr[i];

that is j=16-4=12 and surely ‘j’ is not present in a map.

So it add arr[i] that is ‘4’ into myset.

  • i=2, myset={ 1, 4 }, sum=16;

j=sum-arr[i];

that is j=16-45=-29 and surely ‘j’ will not be in a map.

So it add arr[i] that is ‘45’ into myset.

  • i=3, myset={ 1, 4, 45 }, sum=16;

j=sum-arr[i];

that is j=16-6= 10 and  j is not present in a map.

So it add arr[i] that is ‘6’ into myset.

  • i=4, myset={ 1, 4, 45, 6 }, sum=16;

j=sum-arr[i];

that is j=16-10= 6 and j is present in map.

This is where we find another element of pair. We have already done operation on 16 and 10.

And we print:

“Found elements with the given sum as 16, is (10, 6);

That means two of the elements are present in the array which has a sum equal to “sum”.

Implementation

C++ program for Count pair with Given Sum

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}

Found elements with the given sum as 16 is (10, 6)

Java program for Count pair with Given Sum

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

Complexity Analysis for Count pair with Given Sum

Time Complexity

O(n) as the whole array is needed to be traversed only once.

Space Complexity

O(n) as a hash map has been used to store array elements.

Reference

Translate »