Minimum sum of absolute difference of pairs of two arrays

December 30, 2021

Minimum sum of absolute difference of pairs of two arrays

In Minimum sum of absolute difference of pairs of two arrays Problem we have to find the sum of absolute difference of two arrays. The problem can be solved optimally using greedy technique. In this article we will provide an explanation with C++ code.

Problem Description

Given two integer arrays each of size n. Arrange the arrays such that the sum of absolute difference to elements of two arrays taken pairwise is minimum. Output the minimum difference.

Input

First Line Contains a singe integer n.
Next two line contains n integers each – the array elements.

Output

The minimum difference.

Solution

The problem can be optimally solved using greedy technique.

Since we have to minimize the sum of absolute difference, we need to pair the elements in such a way that the maximum of each array are subtracted with each other, same for second maximum & so on.

Steps –

Sort both the arrays in increasing order.
Iteratively take the difference and add it’s absolute value.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int solve(int A[], int B[], int n)
{
    sort(A, A + n);
    sort(B, B + n);

    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += abs(A[i] – B[i]);

    return sum;
}
int main()
{
    int n;
    cin >> n;
    int A[n], B[n];

    for (int i = 0; i < n; i++)
        cin >> A[i];
    for (int i = 0; i < n; i++)
        cin >> B[i];

    cout << solve(A, B, n) << endl;
    return 0;
}

Output