I used brute force approach but it can not be efficient.Please tell me How to print the all pairs with given sum efficiently???

Like suppose an array with 3 element are (4, 5, 2} and given sum is 6. Then the pair with given sum is

{4,2} and {2,4}

input

3

4 5 2

6

Output :

4 6

2 4

**My

```
[1]**
[1]: http://ideone.com/mN1MTk
```

there is an O(n*log(n)) approach to solve this question.*

letâ€™s suppose arr is the array consisting of all number and sum is the required sum you want to find then,

sort the array and then for every element num in the array find if(sum-num) is there in the array using binary search. now the complexity of this approach is n for iteration and log(n) for binary search so overall time complexity is O(nlog(n)).

O(n) approach :

make a array and store frequency of every element in that array and let that array be mp.

therefore mp[i] will be the frequency of element i.Now for every element num in array just add mp[sum-num] to your answer.Thats your answer.Complexity of this approach is O(n).

2 Likes

@wompowe wonâ€™t that O(n) solution depend on the size of the number of the array and not on the size of the array. An O(n) approach here could be by using 2-pointer technique.

1 Like

@rashedcs First of all he is giving u the solution and I think u should code urself.

**A better solution is possible in O(n) time.**

Below is the **Algorithm.**

1-Create a map to store frequency of each number in the array. (Single traversal is required)

2-In the next traversal, for every element check if it can be combined with any other element (other than itself!) to give the desired sum. Increment the counter accordingly.

3-After completion of second traversal, weâ€™d have twice the required value stored in counter because every pair is counted two times. Hence divide count by 2 and return.

**Code is here for function**:

int getPairsCount(int arr[], int n, int sum)

{

unordered_map<int, int> m;

```
// Store counts of all elements in map m
for (int i=0; i<n; i++)
m[arr[i]]++;
int twice_count = 0;
// iterate through each element and increment the
// count (Notice that every pair is counted twice)
for (int i=0; i<n; i++)
{
twice_count += m[sum-arr[i]];
// if (arr[i], arr[i]) pair satisfies the condition,
// then we need to ensure that the count is
// decreased by one such that the (arr[i], arr[i])
// pair is not considered
if (sum-arr[i] == arr[i])
twice_count--;
}
// return the half of twice_count
return twice_count/2;
```

}

int main()

{

```
int arr[] = {1, 5, 7, -1, 5} ;
int n = sizeof(arr)/sizeof(arr[0]);
int sum = 6;
cout << "Count of pairs is "
<< getPairsCount(arr, n, sum);
return 0;
```

}

edit-complete code

1 Like

**You can use two pointers to solve this problem **

**#include****<**bits/stdc++.h>
#include**<**iostream>
using namespace std;
int main()
{
int n,j,k,i,a[100005];
cin>>n;
for(i=0;i**<**n;i++)
cin>>a[i];
cin>>k;
sort(a,a+n); // sort the array in accending order
i=0;
j=n-1;
while(i**<**j)
{
if(a[i]+a[j]==k)
{
cout**<<**a[i]<<" "**<<**a[j]<<"\n";
cout**<<**a[j]<<" "**<<**a[i]<<"\n";
i++;
j--;
}
else if(a[i]+a[j]<k)
{
i++;
}
else
{
j--;
}
}
return 0;
}

**It solve your problem in O(nlogn)= O(nlogn) + O(n) time complexity **

**O(nlogn)** = sorting

**O(n) ** = loop

For more info take a look : link.

**here one more method using hashmap is also given.**

1 Like

It could not give the right outputâ€¦

Please read the problem again.

Please i have already told you many time, that please search your query at least on google before posting it here. There is already a question given on geeks. You just need to modify this code and your question solved

1 Like

Bro please read carefully the problem againâ€¦I searches stackoverflow, googleâ€¦It is something hardâ€¦

1 Like

I read that tutorialâ€¦but this problem is different from geeksforgeeks tutorialâ€¦Kindly request u , At first read the problem carefullyâ€¦Then Please commentâ€¦

1 Like

#include**<**bits/stdc++.h>
#include **<**iostream>
using namespace std;
int main()
{
map**<**int,int>m;
int n,x,y,sum,i,a[100005];
cin>>n;
for(i=0;i**<**n;i++)
{
cin>>a[i];
m[a[i]]=1;
}
cin>>sum;
map::iterator it,it1;
for(it=m.begin();it!=m.end();++it)
{
x=it->first;
y=sum-x;
it1=m.find(y);
if(it1!=m.end())
cout<**<**x<<" "<**<**y<<"\n";
}
return 0;
}

**THIS will solve your problem in O(nlogn) time complexity**

**The code store all the elements of array using map.and the find the other elment (sum-x) in hash table using â€śfindâ€ť fuction.**

Hope THIS WILL HELP YOU !!

2 Likes

no it only count 1 pair 2,4 which is correct

You are wrong. Itâ€™s complexity will be O(nlogn). Itâ€™s map<> not a unordered_map<>

1 Like

It does not works with above problemâ€¦

ok, sorry my bad , but this can solve the problem effeciently