## 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.

There can be several ways to do, what we found are two methods.

**1 ) Using Sort input Array**

2) Using Hash Map

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.