Check if a given number is the sum of two numbers from two arrays
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (4574)

You are given two integer arrays X and Y . Find all pairs of elements (\( x_i,y_i \)) such that \( x_i\in X \) and \( y_i\in Y \) where \( x_i+y_i = k \).

Posted Answers

  • Sort both arrays in increasing order.
  • Take the sum of the smallest element in X and the largest element in Y . Compare it with k .
  • If the sum is smaller than k , go to the next element in X and repeat step 2 recursively.
  • If the sum is greater than k , go to the previous element in Y and repeat step 2 recursively.
  • If they are equal, pair is found. Continue to find the next pair.

Time complexity to sort the arrays using any comparison based sorting = \( O(nlogn) \).
Time complexity to find the pair using recursion = \( O(n) \).
\( \therefore \) Overall time complexity = \(O(nlogn) \).

If we have any prior knowledge about the range (if it is not too large) of the elements in the two arrays we can use counting sort or radix sort, instead of any comparison based sorting. In that case the time complexity for sorting will be linear which results an overall linear time performance of the algorithm.

You need to Sign In to post your solution.