top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

0 votes
638 views
posted Jun 22, 2014 by Salil Agrawal

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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

1 Answer

+1 vote

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)
answer Jun 22, 2014 by Prakash Singh
Time complexity o(n)
But Taking extra space.
Similar Questions
+3 votes

Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50}
Output: 125 (40, 50, 35)

+1 vote

Say you are given

int a[ ] = {1,2,3,4};
int b[ ] = {4,3,2,1};
int S = 5;

Now the task is to find all pairs of two number which adds up to S (One number from a and other number from b).

+8 votes

Given an array of numbers find all such triplets that satisfy the given condition.

Condition: a[i] < a[j] < a[k] where I < j < k.
Is it possible to do in linear time O(N) ?? if yes how??
if not so what would be optimized approach.

...