2
$\begingroup$

You have two arrays, a and b

Both contain n elements, all positive and distinct.

you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs are minimized.

for example, a = [1, 2, 3], b = [4, 5, 6]

one possible set of pairs = (1, 4), (2, 5), (3, 6)

sum of differences = |1 - 4| + |2 - 5| + |3 - 6| = 9

And now the sum of the differences has to be as small as possible

Desing an algorithm that those this is O(nlogn) time

So far, I have sorted both these arrays. I am unsure how to proceed now

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In fact, you have given the algorithm! Can you see it? Now the task for you is to verify why it works. $\endgroup$
    – John L.
    Jun 17, 2020 at 18:16
  • $\begingroup$ is the algorithm simple solrt both arrays, and then use corresponding elements from each array as matching pairs? and is this the proof? cs.stackexchange.com/questions/21767/… $\endgroup$
    – Sharhad Bashar
    Jun 17, 2020 at 23:57
  • $\begingroup$ Yes, you did it again. $\endgroup$
    – John L.
    Jun 18, 2020 at 1:39

0

Reset to default

Browse other questions tagged or ask your own question.