Given two arrays A[] and B[] both of size N consisting of distinct elements, the task is to find the minimum cost to swap two given arrays. Cost of swapping two elements A[i] and B[j] is min(A[i], A[j]). The total cost is the cumulative sum of the costs of all swap operations.
Note: Here, the order of elements can differ from the original arrays after swapping.
Examples:
Input: N = 3, A[] = {1, 4, 2}, B[] = {10, 6, 12}
Output: 5
Explanation:
Following swap operations will give the minimum cost:
swap(A[0], B[2]): cost = min(A[0], B[2]) = 1, A[ ] = {12, 4, 2}, B[ ] = {10, 6, 1}
swap(A[2], B[2]): cost = min(A[2], B[2]) = 1, A[ ] = {12, 4, 1}, B[ ] = {10, 6, 2}
swap(A[2], B[0]): cost = min(A[2], B[0]) = 1, A[ ] = {12, 4, 10}, B[ ] = {1, 6, 2}
swap(A[1], B[0]): cost = min(A[1], B[0]) = 1, A[ ] = {12, 1, 10}, B[ ] = {4, 6, 2}
swap(A[1], B[1]): cost = min(A[1], B[1]) = 1, A[ ] = {12, 6, 10}, B[ ] = {4, 1, 2}
Therefore, the minimum cost to swap two arrays = 1 + 1 + 1 + 1 + 1 = 5
Input: N = 2, A[] = {9, 12}, B[] = {3, 15}
Output: 9
Approach:
Follow the steps below to solve the problem:
- Traverse the arrays simultaneously and find the minimum element from them, say K.
- Now, every element with K until the two arrays are swapped. Therefore, the number of swaps required is 2*N – 1.
- Print K * (2 * N – 1) as the answer.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate and return the// minimum cost required to swap two arraysint getMinCost(vector<int> A, vector<int> B, int N){ int mini = INT_MAX; for (int i = 0; i < N; i++) { mini = min(mini, min(A[i], B[i])); } // Return the total minimum cost return mini * (2 * N - 1);}// Driver Codeint main(){ int N = 3; vector<int> A = { 1, 4, 2 }; vector<int> B = { 10, 6, 12 }; cout << getMinCost(A, B, N); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to calculate and return the// minimum cost required to swap two arraysstatic int getMinCost(int [] A, int [] B, int N){ int mini = Integer.MAX_VALUE; for (int i = 0; i < N; i++) { mini = Math.min(mini, Math.min(A[i], B[i])); } // Return the total minimum cost return mini * (2 * N - 1);}// Driver Codepublic static void main(String[] args){ int N = 3; int [] A = { 1, 4, 2 }; int [] B = { 10, 6, 12 }; System.out.print(getMinCost(A, B, N));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to implement# the above approachimport sys# Function to calculate and return the# minimum cost required to swap two arraysdef getMinCost(A, B, N): mini = sys.maxsize for i in range(N): mini = min(mini, min(A[i], B[i])) # Return the total minimum cost return mini * (2 * N - 1)# Driver CodeN = 3A = [ 1, 4, 2 ]B = [ 10, 6, 12 ]print(getMinCost(A, B, N))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to calculate and return the // minimum cost required to swap two arrays static int getMinCost(int[] A, int[] B, int N) { int mini = int.MaxValue; for (int i = 0; i < N; i++) { mini = Math.Min(mini, Math.Min(A[i], B[i])); } // Return the total minimum cost return mini * (2 * N - 1); } // Driver Code public static void Main(String[] args) { int N = 3; int[] A = {1, 4, 2}; int[] B = {10, 6, 12}; Console.Write(getMinCost(A, B, N)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Java script program to implement// the above approachfunction getMinCost(A,B,N){ let mini = Number.MAX_VALUE; for (let i = 0; i < N; i++) { mini = Math.min(mini, Math.min(A[i], B[i])); } // Return the total minimum cost return mini * (2 * N - 1);}// Driver Code let N = 3; let A = [ 1, 4, 2 ]; let B = [ 10, 6, 12 ]; document.write(getMinCost(A, B, N));// This code is contributed by manoj</script> |
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
