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;
}