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

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