# 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 for Both Methods:

 import java.util.*; public class TwoNumbersInArray { private int[] arrA; private int number; public TwoNumbersInArray(int[] arrA, int number) { this.arrA = arrA; this.number = number; } public Boolean usingBinarySearch() { // 1. First sort the array Arrays.sort(arrA); // 2. now do the linear scan to the from the left array , say starting // index i=0 // 3. Calculate Rem_Sum = number – a[i] // 4. if Rem_Sum<0, move to the next element // 5. if Rem_Sum>0, Perform Binary Search on the remaining elements on // the right side. for (int i = 0; i < arrA.length – 1; i++) { int RemS = number – arrA[i]; if (RemS > 0) { if (binarySearch(i + 1, arrA.length – 1, RemS)) return true; } } return false; } public Boolean binarySearch(int low,int high, int number){ if(low>high){ return false; } int mid = low + ((high – low) / 2); if(arrA[mid]==number)return true; else if (arrA[mid]>number) return binarySearch(low,mid–1,number); else return binarySearch(mid+1,high,number); } public Boolean usingBothEnds() { // 1. First sort the array Arrays.sort(arrA); // 2. Start from the both ends of the array // 3. add first (say 'a') and last element(say 'b') of the array say S // 4. if S > number , S = S-(last_element) + (element before that) // 5. if S < number , S = S – (first element) + (next element) // 6. if S=number, return true // 7. Repeat step // 8. If iteration gets over and retrun false. int i = 0; int j = arrA.length – 1; int Sum = 0; while (i != j) { Sum = arrA[i] + arrA[j]; if (Sum == number) return true; else if (Sum < number) i++; else if (Sum > number) j—; } return false; } public static void main(String[] args) { int a[] = { 1, 2, 3, 4, 5, 16, 17, 18, 19, 249 }; int number = 269; int number1 = 8; TwoNumbersInArray tn = new TwoNumbersInArray(a, number); System.out.println("USING Both Ends -Sum of two numbers in array A is " + number + " ??? :" + tn.usingBothEnds()); System.out .println("USING Binary Search -Sum of two numbers in array A is " + number + " ??? :" + tn.usingBinarySearch()); TwoNumbersInArray tn1 = new TwoNumbersInArray(a, number1); System.out.println("USING Both Ends -Sum of two numbers in array A is " + number1 + " ??? :" + tn1.usingBothEnds()); System.out .println("USING Binary Search -Sum of two numbers in array A is " + number1 + " ??? :" + tn1.usingBinarySearch()); } }

```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
```