Minimum sum of absolute difference of pairs of two arrays

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.

Examples:

Input :  a[] = {3, 2, 1}
         b[] = {2, 1, 3}
Output : 0

Input :  n = 4
         a[] = {4, 1, 8, 7}
         b[] = {2, 3, 6, 5}
Output : 6
class Solution {
    public long findMinSum(long a[], long b[], long n) {
        Arrays.sort(a);
        Arrays.sort(b);
        long sum = 0;
        for (int i = 0; i < n; i++)
            sum = sum + Math.abs(a[i] - b[i]);
        return sum;
    }
}

Last updated