Description: In an array of size ‘n’ find a pair of numbers which add up to a given no. ‘x’.

 
If video does not load, Click here
Example:

1  3  2  18  6  8  4  15 7

If x=17 in the above example, the 2 numbers are 2 and 15.

Algorithm:
 
  1. Sort the elements of the array using merge-sort in increasing order.
  2. Intialize ‘p’ as first index(0) and ‘q’ as last index(n-1).
  3. Iteratively perform the following operations:

     -If arr[p]+arr[q]==x, PRINT VALUES of arr[p] and arr[q] and break out of the loop.

     -Else if, arr[p]+arr[q]>x,

      q=q-1;

     -Else,

      p=p+1

Implementation in C:

void quickSort(int *, int, int);
 
/* Function to find if the pair exists  or not*/
 
int TwoCandidates(int A[], int arr_size, int sum)
{
    int l, r;
 
    /* Sort the elements */
    quickSort(A, 0, arr_size-1);
 
    /* Now look for the two candidates in the sorted array*/
    l = 0;
    r = arr_size-1;
    while(l < r)
    {
         if(A[l] + A[r] == sum)
              return 1;
         else if(A[l] + A[r] < sum)
              l++;
         else /* A[i] + A[j] > sum */
              r--;
    }   
    return 0;
}
 

/* FOLLOWING FUNCTIONS ARE USED FOR SORTING */
void exchange(int *a, int *b)
{
    int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}
 
int partition(int A[], int si, int ei)
{
    int x = A[ei];
    int i = (si - 1);
    int j;
 
    for (j = si; j <= ei - 1; j++)
    {
        if(A[j] <= x)
        {
            i++;
            exchange(&A[i], &A[j]);
        }
    }
    exchange (&A[i + 1], &A[ei]);
    return (i + 1);
}
 
void quickSort(int A[], int si, int ei)
{
    int pi;    /* Partitioning index */
    if(si < ei)
    {
        pi = partition(A, si, ei);
        quickSort(A, si, pi - 1);
        quickSort(A, pi + 1, ei);
    }
}
 Time Complexity:

O(nlgn)

Go to top