Find pairs of numbers with certain sum

0
votes

Consider 2 arrays of positive integers. We are given some predefined integer constant N. Now, we must find pairs, where 1 element brought from 1 array, and 2 - from second array, such that sum of integers equals N. If no such pairs found, return pairs, which sum is closest(but doesn't exceed) to N (it can be several pairs, if they have equal sum)

I have the only solution in my mind : Traverse all possible pairs, if we encounter pair of closer distance, clean resulting array and put it there. If we encounter the pair of exact distance, clear pairs with lower distance and put the pair into resulting array.

I believe there is more efficient way to solve the problem, do you have any ideas on that?

1
algorithm
Sort arrays, travel only a few elements by binary-like search. – huseyin tugrul buyukisik

1 Answers

0
votes

So we have array A and B and we want to find out 

  a + b <= N   where a belongs to A and b belongs to B

such that

  (N - a - b) is minimum

We can do the follow

  1. Sort B array : |B| * log('B') time complexity
  2. For each a in A find the closest to N - a value (b) in B array with a help of binary search : |A| * log(|B|) time complexity
  3. Track the best (minimum) a and b pairs

Total time complexity

|B| * log('B') + |A| * log(|B|) = (|A| + |B|) * log(|B|)

In case |B| > |A| we can sort A array and scan B and have (|A| + |B|) * log(|A|) time complexity

If |A| ~ |B| ~ M we have M * log(M) time complexity