Be the first user to complete this post

Add to List 
Find a pair of numbers from an array whose sum equals k
Objective: Write an algorithm to find out whether in a given array there exists or not two numbers whose sum is exactly equals to a given number. This problem has been asked in Amazon and Microsoft interviews.
Input: An array arrA[], A number k
Output: True or false based upon we have found any two numbers in array arrA[] whose sum is equal to k
Approach:
Method 1: Using Binary Search
 First sort the array using Merge Sort(To know about Merge Sort and its implementation Click Here)
 Now do the linear scan to the from the left array , say starting index i=0
 Calculate Rem_Sum = number  arrA[i]
 If Rem_Sum<0, move to the next element
 If Rem_Sum>0, Perform Binary Search for Rem_Sum on the remaining elements on the right side.
Time Complexity  O(nlogn)
Method 2: Using Both Ends
 First sort the array using Merge Sort(To know about Merge Sort and its implementation Click Here)
 Start from the both ends of the array
 Add first (say 'a') and last element(say 'b') of the array say S
 If S > number , S = S(last_element) + (element before that)
 If S < number , S = S  (first element) + (next element)
 If if S=number, return true
 Repeat step
 If iteration gets over and retrun false.
Code:
Output
: USING Both Ends Sum of two numbers in array A is 269 ??? :false USING Binary Search Sum of two numbers in array A is 269 ??? :false USING Both Ends Sum of two numbers in array A is 8 ??? :true USING Binary Search Sum of two numbers in array A is 8 ??? :true
Also Read: