Find Minimum Cost to Match Arrays A and B as Permutations

Given two array A[] and B[] of length N, the task is the find the minimum cost to make array A[] a permutation of array B[], where the cost of incrementing or decrementing an element by 1 is 1.

Note: You are allowed to increase or decrease only 1 element of A at a time.

Examples:

Input : A[] = {1, 2, 2}, B[] = {10, 5, 1}
Output : 11
Explanation : 
One possible permitation of B with minimum cost is [1, 5, 10].
Hence the cost is abs(1-1) + abs(2-5) + abs(2-10) = 0 + 3 + 8 = 11

Input : A[] = {2, 5, 8, 1, 3, 9}, B[] = {1, 2, 5, 3, 9, 0}
Output : 8
Explanation : 
The permitation of B[] giving minimum cost is {0, 1, 2, 3, 5, 9}.

Recommended: Why Learn C++?

Approach:

The permutation of array B[] that can be made from array A[] by incrementing or decrementing elements of A[] in minimum cost is sorted array B[].

Sort both arrays A[] and B[].
Iterate through both array and add to cost abs(A[i] - B[i]).
Finally return the cost.

Below is the implementation of the above approach:

#include <iostream>
#include <algorithm>
using namespace std;

// Function to minimum required cost
int minCostPermutation(int A[], int B[], int N) {
    // Sort both arrays
    sort(A, A + N);
    sort(B, B + N);

    // Variable to store cost
    int cost = 0;

    // Loop through arrays to find min cost
    for (int i = 0; i < N; ++i)
        cost += abs(A[i] - B[i]);

    return cost;
}

// Driver code
int main() {
    int A[] = {2, 5, 8, 1, 3, 9}, B[] = {1, 2, 5, 3, 9, 0};
    int N = sizeof(A) / sizeof(A[0]);

    // Function to find required answer
    cout << minCostPermutation(A, B, N);

    return 0;
}

Output :

Time Complexity : O(nlogn)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.