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

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.

Complete 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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • eugen_nw

    I’d think that after executing line #22, if RemS is negative we should break out of that loop. That’s because arrA is sorted in ascending order, so all subsequent instances of RemS will be also negative.

%d bloggers like this: