Show all pairs with given sum

general
5

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
6

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
7 
#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
8

Hope this geeks for geeks link will help. LINK

9

@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
10 
   #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

11

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

12

Please give ur code…

13

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

14

yeap…

15

It could not give the right output…

16

Please read the problem again.

17

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

1 Like
18

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
19

test case plz?

20

input
3
4 5 2
6

Output :
4 6
2 4

21

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

22

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

1 Like
23

It does not works with above problem…

24

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