Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find a pair of numbers from an array whose sum equals k

Objec­tive: Write an algo­rithm to find out whether in a given array there exists or not two num­bers whose sum is exactly equals to a given num­ber. This prob­lem has been asked in Ama­zon and Microsoft interviews.

Input: An array arrA[], A num­ber k

Out­put: True or false based upon we have found any two num­bers in array arrA[] whose sum is equal to k

Approach:

Method 1: Using Binary Search

Time Com­plex­ity — O(nlogn)

Method 2: Using Both Ends

  • First sort the array using Merge Sort(To know about Merge Sort and its imple­men­ta­tion 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 > num­ber , S = S-(last_element) + (ele­ment before that)
  • If S < num­ber , S = S — (first ele­ment) + (next element)
  • If if S=number, return true
  • Repeat step
  • If iter­a­tion gets over and retrun false.

Com­plete 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

You may also like...

  • eugen_nw

    I’d think that after exe­cut­ing line #22, if RemS is neg­a­tive we should break out of that loop. That’s because arrA is sorted in ascend­ing order, so all sub­se­quent instances of RemS will be also negative.