Show all pairs with given sum

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(nlog(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(n
log(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).

3 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

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

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 :slight_smile:

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

Hope this geeks for geeks link will help. LINK

@mathecodician in @wompowe’s explanation,using map is better than array as that will be able to handle negative as well as large numbers but as he has used array instead of map this would be able to solve numbers upto 10^8 only.

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

   map<int, int>Map;

   void subsetSum(int arr[], int n, int kvalue)
   {
      for(int i=0; i<n; i++)
      {
        //Map[arr[i]]++;
         if(Map.count(kvalue-arr[i]))
         {
            cout<<arr[i]<<" "<<kvalue-arr[i]<<"\n";
         }
      }
   }


   int main()
   {
      int n, x, y, sum;
      int arr[100];

      cin>>n>>sum;
      for(int i=0; i<n; i++)
      {
        cin>>arr[i];
        Map[arr[i]]++;
      }
      subsetSum(arr, n, sum);

      return 0;
    }

link

Python 3

num=int(input())

n=int(input())

a=[int(x) for x in input().strip().split(" ")]

a.sort()

i,j=0,(len(a)-1)

count=0

while i<j:

if a[i]+a[j]==num:

    count+=1

    if a[i+1]+a[j]==num:

        count+=1

        i+=1

    elif (a[j-1]+a[i])==num:

        count+=1

        j-=1

    i+=1

    j-=1

elif a[i]+a[j]<num:

    i+=1

else:

    j-=1

print(count)

Kindly ignore the indentation and put it wherever required

Please give ur code…

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

yeap…

It could not give the right output…

Please read the problem again.

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

test case plz?

input
3
4 5 2
6

Output :
4 6
2 4