Question: Given an integer array, find any 2 numbers which adds to a given integer. Return FALSE if no 2 such number exists.


Ex: array A[]= {3, 1, 8, 11, 5, 7}

given integer say N = 6
answer will be 1,5.

If N would be 5, answer will be FALSE.

Answer: A simple brute force approach may be to look for N-A[i] for every i from 0 to length of A. This will be an O(N^2) approach. If array is sorted, we can search N-A[i] in O(NlogN) time. Can we do better than this?

Not for unsorted array but for sorted array, we can certainly do better. It will add O(NlogN) time for sorting. (Time efficiency will be same as earlier binary search approach coz of sorting time but total number of comparison will be less.)

Algorithm:

Sort array A[]
initialize 2 pointers. 
Start <= begining of the array A; 
end <= end of A 
while start < end 
  if A[start] + A[end] < N 
    increase start by 1 
  else if A[start] + A[end] == N 
    return 
  else 
    decrease end by 1 
end while 
return FALSE

Code:
bool sum_euqal_to_N(int A[], int N)
{
 int start = 0;
 int end = MAX-1;
 
 //check for boundary conditions
 if ((A[start]+A[start+1]) > N)
  return false;
 
 if ((A[end]+A[end+1]) < N)
  return false;
 
 
 while (end > start)
 {
  if ((A[start] + A[end]) < N)
   start++;
  else if ((A[start] + A[end]) == N)
  {
   cout << A[start] << " " << A[end] << endl;
   return true;
  }
  else
   end--;
 }
 
 return false;
}


Efficiency: if input array A is sorted then O(N).
else O(NlogN) coz of sorting time NlogN.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.