Find a pair of elements from an array whose sum equals a given number

Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X.

Algorithm:
(1) Sort the array in ascending order. Use quick sort O(n logn), we mentioned in our previous post.
(2) Initialize two index variables to find the candidate
elements in the sorted array.

  • Initialize the leftmost index: left = 0
  • Initialize the rightmost index: right = arr_size-1

(3) Loop while left < right

  •  If (A[left] + A[right] == sum) then return true
  • Else if( A[left] + A[right] < sum ) then left++
  • Else if( A[left] + A[right] > sum ) then right–

(4) No such pair – return o

void findpair(int arr[], int len, int sum)
{
    std::sort(arr, len); // sort the input array
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << arr[i] << "," << arr[j];
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << arr[i] << "," << arr[j];
            j--;
        }
    }
}
// main program to test the above function
int main()
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,10};
    findpair(arr, 10, 7);
}

Output:  3,4
Complexity:  O(nLog(n)+n)

Method 2: With O(N) time complexity using extra space

1. Take a binary Map.
2. Now traverse the array
2.1 check sum-arr[i] is set if set you have found one pair.
2.2 set arr[i] in array.

#include<iostream>
#define MAX 1000
using namespace std;
void findPairs(int *arr,int N,int sum)
{    
	bool map[MAX]={0};      

	for(int i=0;i<N;i++)
	{
		int dif = sum-arr[i];
		if(dif>=0 && map[dif]==1)
			cout<<"Pair with given sum are "<<arr[i]<<" and "<<dif;
		map[arr[i]]=1;
	}
} 
/* Driver program to test above function */
int main()
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    int arr_size = 6;
 
    findPairs(A, arr_size, n);
 
    getchar();
    return 0;
}

2 Thoughts on “Find a pair of elements from an array whose sum equals a given number

  1. Amit Gaur on July 8, 2013 at 8:33 pm said:

    O(N) approach with O(X) space complexity will only work if array contains +ve integers.

    1. create an array of size X.
    2. now traverse the array
    2.1 check X-arr[i] is set if set you have found one pair.
    2.2 set arr[i] in array.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation