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,mid1,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