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}.
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 :
8
Time Complexity : O(nlogn)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.