Given an array A[] and a number x, check for pair in A[] with sum as x
Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.
There can be several ways to do, what we found are two methods.
1 ) Using Sort input Array 2) Using Hash Map
Algorithm with Example with Sorting Array
findPair (A[], sum)
//A = {1, 4, 6, 9, -3 , 12, 2}
//sum = 10
1) len = Length of A[]
//len = 8
2) Sort the array in increasing order.
//A = {-3,1,2,3,4,6,9,12}
3) Initialize two variables on starting and ending
(a) Initialize first to the leftmost index: lt = 0
(b) Initialize second the rightmost index: rt = len-1
4) Loop while lt < rt.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then lt++
(c) Else rt--
//First Iteration:
//a)lt=0 , rt=7 , -3+12 != 10
//b)-3+12 = 9 < 10 =>; lt=lt++ =>; lt = 1.
//Second Iteration :
//a) lt=1, rt =7 , 1+12 !=10
//b) 1+12 =13 > 10, =>; rt=len-1=>; rt=6
//Third Iteration :
//a)lt=1, rt=6 , 1+9 =10 =>; Return 1.
5) No candidates in whole array : return 0
Time Complexity : O(nlogn) (for merge if Merge or Heap sort is used.)
Space Complexity : O(n)( for Merge sort) O(1) for heap sort.
Algorithm with Example for Using Hash map
Let A be the given array.
And X be the give sum
len = A.length
for i=0 to len{
hash(A[i]) = i // key is the element and value is its index.
}
//Hash is created with index and element.
for i=0 to len{
if hash(X - A[i]) != j // if (X - element) exists and is different we found a pair
{
print "pair i , j has sum K"
}//if
}//for
Searching in Hash takes O(1).
So what we do is
take first element and if its counter number which makes sum X exists then print both number.
example
A = {-3,1,2,3,4,6,9,12}
A[0] = -3
What we search in condition if hash(X - A[i]) != i
if(10-(-3))=13 exist for some 'j' then
element at i (=-3) and j(=13) makes sum 10.
Time Complexity : O(N)
Space Complexity : O(N) for storing Hash.
