Find pairs in array with given sum

Write a program to find all the pairs in array that sum to some number.

solution

Given an array of size n we need to find the pair of elemnts in that array which total to particular sum value.
For eg:- for n=7
a[]={5 ,2 ,3 ,4 ,1 ,6 ,7}
and desired sum value =7;
Output of program =
5 2
3 4
6 1.
thus all the pairs that total to given sum value are printed.

Simplest approach:-
The most simplest approach is that for each and every element we search for its counterpart that makes the sum of both equal to desired sum. SInce we need to search counterparts for each elemnt therefore the array had to be traversed completely for each element .
Thus, the complexity of this program comes out to be O(n*n).

code

[code language=”cpp”]

#include <iostream>
using namespace std;

int main() {
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>sum;
for(int i=0;i<n;i++)
for(j=i;j<n;j++)
{if(a[i]+a[j]==sum)
cout<<a[i]<< "  "<<a[j]<<endl;}
return 0;
}
[/code]

However this approach is much more time consuming. In order to optimise this and reduce the time complexity we use hash map based approach.

The code for hash-map based approach is as follows

 

[code language=”cpp”]
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
/*Write a C program that, given an array A[] of n numbers and another number x,
determines whether or not there exist two elements in S whose sum is exactly x.*/
int n,i,sum;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
cin>>sum;
unordered_set<int> s;// using unordered set we search the desired number in O(1)
for(i=0;i<n;i++)
{
int temp=sum-a[i];
if(temp>=0 && s.find(temp)!=s.end())
cout<<a[i]<<" "<<temp<<endl;
else
s.insert(a[i]);
}
return 0;
}

[/code]

 

Please Login/Signup to comment