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: