Question

How we can find all non duplicate pairs of an array which has a sum S.

Comments

sir.... is this sum a specific value or just a sum of two non duplicate value of pair??

---

Sum here is specific value..:)

---

Step 1: Sort the array say u chose QuickSort then it will take O(nlogn).
Step 2: Take two pointers p1 and p2, p1 pointing at first and p2 pointing at last element in the list. Now if the sum is less then S, move p1 forward, if sum is greater then S move p2 backward, if equal then store in a repository.
Step 3: Keep doing step 2 until p1 and p2 crosses each other.
Step 4: Step 2 & 3 should take O(n) time.

Total complexity = O(nlogn) + O(n) = O(nlogn)

Guys correct me if I am wrong

Answer 1

Simple Logic storing the value at the index of the array and then it became lot simple...

#include<iostream>
using namespace std;

void findAllNdup(int  arr[], int count[], int n, int s)
{
      for( int i =0; i< n; i++)
      {
          count[arr[ i]]++;
      }

      for( int j= 0; j< n; j++)
      {
          if( count[arr[ j]] != 0 && count[s- arr[ j]] !=0)
          {
             cout<<"("<< arr[ j]<<","<< s- arr[j]<<")"<< endl;
             count[s- arr[ j]]=0;
           }
       }
}

int main()
{
    int arr[] ={2,1,3,6,7,5,3,5,8,4,9,1};
    int count[10]={0};
    int sum =10;
    int size = sizeof(arr)/sizeof(arr[0]);
    findAllNdup(arr, count, size, sum);
    return 0;
}

Output

(2,8)
(1,9)
(3,7)
(6,4)
(5,5)

Comments

Time complexity o(n)
But Taking extra space.