## Saturday, April 22, 2017

### Minimum sum of absolute difference of pairs of two arrays - GeeksforGeeks

Minimum sum of absolute difference of pairs of two arrays - GeeksforGeeks
Given two arrays a[] and b[] of equal length n. The task is to pair each element of array a to an element in array b, such that sum S of absolute differences of all the pairs is minimum.
Suppose, two elements a[i] and a[j] (i != j) of a are paired with elements b[p] and b[q] of b respectively,
then p should not be equal to q.

The solution to the problem is a simple greedy approach. It consists of two steps.
Step 1 : Sort both the arrays in O (n log n) time.
Step 2 : Find absolute difference of each pair of corresponding elements (elements at same index) of both arrays and add the result to the sum S. The time complexity of this step is O(n).

`long` `long` `int` `findMinSum(``int` `a[], ``int` `b[], ``int` `n)`
`{`
`    ``// Sort both arrays`
`    ``sort(a, a+n);`
`    ``sort(b, b+n);`

`    ``// Find sum of absolute differences`
`    ``long` `long` `int` `sum= 0 ;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``sum = sum + ``abs``(a[i]-b[i]);`

`    ``return` `sum;`
`}`