Show all pairs with given sum

general
21

Hope this geeks for geeks link will help. LINK

22

code is working…ur problem solution is here-https://youtu.be/j613i8sigE0

this will clear ur all doubts

23

dear, can you explain that “4 6”? If I am getting the Q correctly, we need to print the pairs, right? Shouldn’t it be “4 2” and “2 4”? Or am I missing something? Also, is there any constraint/info regarding order in which pairs must be printed??

24

Please tell the logic of this code…

25

He mentioned in comments that he already read it. But he would appreciate if you can give some solution from your side :slight_smile:

26

Nice tutorial …Tnq @vivek96

1 Like
27

first loop : First store all the elements of the array with key/value pair (map table).
second loop : take a element from the map table (say x) , then find the other element (say y) such that y==(sum-x) using FIND function.
If found print both element i.e, X and Y .

1 Like
28

is it possible in O(nlogn)?

29

@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
30

if you want to print all unique pairs of numbers, then solutions given here are mostly ok, but if you want to print all pairs of indices (i, j) for which a[i] + a[j] = k, where k is your sum, then there is no way to do this in general faster than O(n^2), because there are O(n^2) such pairs of indices.

3 Likes
31

Sure. Have mid-sem in one hour. Will give by today.

1 Like
32

please accept the answer if u like this content.

33

All the best dear! I can feel your pain :stuck_out_tongue:

34

@pkacprazak - Can we not just add another line to print indices (j,i) along with (i,j)? Will it still be inefficient?

35

If i want to find the unique output …Then what is change in this code???

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

37

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