Given two arrays A[] and B[] consisting of M and N integers respectively, and an integer C, the task is to find the minimum cost required to make the sequence A exactly the same as B(consists of distinct elements only) by performing the following operations on array A[]:
- Remove any element from the array with cost 0.
- Insert a new element anywhere in the array with cost C.
Examples:
Input: A[] = {1, 6, 3, 5, 10}, B[] = {3, 1, 5}, C = 2
Output: 2
Explanation:
Removing elements 1, 6, and 10 from the array costs 0. The array A[] becomes {3, 5}.
Add 1 in between 3 and 5, then the array arr[] becomes {3, 1, 5} which is the same as the array B[].
The cost of above operation is 2.Input: A[] = {10, 5, 2, 4, 10, 5}, B[] = {5, 1, 2, 10, 4}, C = 3
Output: 6
Explanation:
Removing elements 10, 10, and 5 from the array costs 0. The array A[] becomes {5, 2, 4}.
Add element 1 and 10 in the array as {5, 1, 2, 10, 4} which is the same as the array B[].
The cost of above operation is 3*2 = 6.
Naive Approach: The simplest approach is to erase all the elements from array A[] which are not present in array B[] by using two for loops. After that generate all permutations of the remaining element in the array and for each sequence check for the minimum cost such that the array A[] is the same as the array B[]. Print the minimum cost of the same.
Time Complexity: O(N!*N*M), where N is the size of the array A[] and M is the size of the array B[].
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to first find the length of the longest common subsequence of array A[] and B[] and subtract it from the size of array B[], which gives the number of elements to be added in array A[]. And add amount C into the cost for every new element added. Therefore, the total cost is given by:
Cost = C*(N – LCS(A, B))
where,
LCS is the longest common subsequence of the arrays A[] and B[],
N is the length of the array A[], and
C is the cost of adding each element in the array B[].
Follow the steps below to solve the problem:
- Create a new array say index[] and initialize it with -1 and an array nums[].
- Map each element of the array B[] to its corresponding index in the array index[].
- Traverse the given array A[] and insert the values with its mapped values i.e., index number into the array nums[] array and if the index number is not -1.
- Now find the Longest Increasing Subsequence of the array nums[] to obtain the length of the longest common subsequence of the two given arrays.
- After finding the LCS in the above steps, find the value of cost using the formula discussed above.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find length of the// longest common subsequenceint findLCS(int* nums, int N){ int k = 0; for (int i = 0; i < N; i++) { // Find position where element // is to be inserted int pos = lower_bound(nums, nums + k, nums[i]) - nums; nums[pos] = nums[i]; if (k == pos) { k = pos + 1; } } // Return the length of LCS return k;}// Function to find the minimum cost// required to convert the sequence A// exactly same as Bint minimumCost(int* A, int* B, int M, int N, int C){ // Auxiliary array int nums[1000000]; // Stores positions of elements of A[] int index[1000000]; // Initialize index array with -1 memset(index, -1, sizeof(index)); for (int i = 0; i < N; i++) { // Update the index array with // index of corresponding // elements of B index[B[i]] = i; } int k = 0; for (int i = 0; i < M; i++) { // Place only A's array values // with its mapped values // into nums array if (index[A[i]] != -1) { nums[k++] = index[A[i]]; } } // Find LCS int lcs_length = findLCS(nums, k); // No of elements to be added // in array A[] int elements_to_be_added = N - lcs_length; // Stores minimum cost int min_cost = elements_to_be_added * C; // Print the minimum cost cout << min_cost;}// Driver Codeint main(){ // Given array A[] int A[] = { 1, 6, 3, 5, 10 }; int B[] = { 3, 1, 5 }; // Given C int C = 2; // Size of arr A int M = sizeof(A) / sizeof(A[0]); // Size of arr B int N = sizeof(B) / sizeof(B[0]); // Function Call minimumCost(A, B, M, N, C); return 0;} |
Java
// Java program for the above approach import java.io.*;class GFG{ // Function to find lower_boundstatic int LowerBound(int a[], int k, int x){ int l = -1; int r = k; while (l + 1 < r) { int m = (l + r) >>> 1; if (a[m] >= x) { r = m; } else { l = m; } } return r;} // Function to find length of the// longest common subsequencestatic int findLCS(int[] nums, int N){ int k = 0; for(int i = 0; i < N; i++) { // Find position where element // is to be inserted int pos = LowerBound(nums, k, nums[i]); nums[pos] = nums[i]; if (k == pos) { k = pos + 1; } } // Return the length of LCS return k;}// Function to find the minimum cost// required to convert the sequence A// exactly same as Bstatic int minimumCost(int[] A, int[] B, int M, int N, int C){ // Auxiliary array int[] nums = new int[100000]; // Stores positions of elements of A[] int[] index = new int[100000]; // Initialize index array with -1 for(int i = 0; i < 100000; i++) index[i] = -1; for(int i = 0; i < N; i++) { // Update the index array with // index of corresponding // elements of B index[B[i]] = i; } int k = 0; for(int i = 0; i < M; i++) { // Place only A's array values // with its mapped values // into nums array if (index[A[i]] != -1) { nums[k++] = index[A[i]]; } } // Find LCS int lcs_length = findLCS(nums, k); // No of elements to be added // in array A[] int elements_to_be_added = N - lcs_length; // Stores minimum cost int min_cost = elements_to_be_added * C; // Print the minimum cost System.out.println( min_cost); return 0;}// Driver codepublic static void main(String[] args){ // Given array A[] int[] A = { 1, 6, 3, 5, 10 }; int[] B = { 3, 1, 5 }; // Given C int C = 2; // Size of arr A int M = A.length; // Size of arr B int N = B.length; // Function call minimumCost(A, B, M, N, C);}}// This code is contributed by sallagondaavinashreddy7 |
Python3
# Python3 program for the above approach # Function to find lower_bounddef LowerBound(a, k, x): l = -1 r = k while (l + 1 < r): m = (l + r) >> 1 if (a[m] >= x): r = m else: l = m return r # Function to find length of the# longest common subsequencedef findLCS(nums, N): k = 0 for i in range(N): # Find position where element # is to be inserted pos = LowerBound(nums, k, nums[i]) nums[pos] = nums[i] if (k == pos): k = pos + 1 # Return the length of LCS return k # Function to find the minimum cost# required to convert the sequence A# exactly same as Bdef minimumCost(A, B, M, N, C): # Auxiliary array nums = [0] * 100000 # Stores positions of elements of A[] # Initialize index array with -1 index = [-1] * 100000 for i in range(N): # Update the index array with # index of corresponding # elements of B index[B[i]] = i k = 0 for i in range(M): # Place only A's array values # with its mapped values # into nums array if (index[A[i]] != -1): k += 1 nums[k] = index[A[i]] # Find LCS lcs_length = findLCS(nums, k) # No of elements to be added # in array A[] elements_to_be_added = N - lcs_length # Stores minimum cost min_cost = elements_to_be_added * C # Print the minimum cost print( min_cost)# Driver Code# Given array A[]A = [ 1, 6, 3, 5, 10 ]B = [ 3, 1, 5 ] # Given CC = 2 # Size of arr AM = len(A) # Size of arr BN = len(B) # Function callminimumCost(A, B, M, N, C)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System; class GFG{ // Function to find lower_boundstatic int LowerBound(int[] a, int k, int x){ int l = -1; int r = k; while (l + 1 < r) { int m = (l + r) >> 1; if (a[m] >= x) { r = m; } else { l = m; } } return r;} // Function to find length of the// longest common subsequencestatic int findLCS(int[] nums, int N){ int k = 0; for(int i = 0; i < N; i++) { // Find position where element // is to be inserted int pos = LowerBound(nums, k, nums[i]); nums[pos] = nums[i]; if (k == pos) { k = pos + 1; } } // Return the length of LCS return k;} // Function to find the minimum cost// required to convert the sequence A// exactly same as Bstatic int minimumCost(int[] A, int[] B, int M, int N, int C){ // Auxiliary array int[] nums = new int[100000]; // Stores positions of elements of A[] int[] index = new int[100000]; // Initialize index array with -1 for(int i = 0; i < 100000; i++) index[i] = -1; for(int i = 0; i < N; i++) { // Update the index array with // index of corresponding // elements of B index[B[i]] = i; } int k = 0; for(int i = 0; i < M; i++) { // Place only A's array values // with its mapped values // into nums array if (index[A[i]] != -1) { nums[k++] = index[A[i]]; } } // Find LCS int lcs_length = findLCS(nums, k); // No of elements to be added // in array A[] int elements_to_be_added = N - lcs_length; // Stores minimum cost int min_cost = elements_to_be_added * C; // Print the minimum cost Console.WriteLine(min_cost); return 0;} // Driver codepublic static void Main(){ // Given array A[] int[] A = { 1, 6, 3, 5, 10 }; int[] B = { 3, 1, 5 }; // Given C int C = 2; // Size of arr A int M = A.Length; // Size of arr B int N = B.Length; // Function call minimumCost(A, B, M, N, C);}}// This code is contributed by code_hunt |
Javascript
<script>// javascript program for the above approach // Function to find lower_bound function LowerBound(a , k , x) { var l = -1; var r = k; while (l + 1 < r) { var m = (l + r) >>> 1; if (a[m] >= x) { r = m; } else { l = m; } } return r; } // Function to find length of the // longest common subsequence function findLCS(nums , N) { var k = 0; for (i = 0; i < N; i++) { // Find position where element // is to be inserted var pos = LowerBound(nums, k, nums[i]); nums[pos] = nums[i]; if (k == pos) { k = pos + 1; } } // Return the length of LCS return k; } // Function to find the minimum cost // required to convert the sequence A // exactly same as B function minimumCost(A, B , M , N , C) { // Auxiliary array var nums = Array(100000).fill(0); // Stores positions of elements of A var index = Array(100000).fill(0); // Initialize index array with -1 for (i = 0; i < 100000; i++) index[i] = -1; for (i = 0; i < N; i++) { // Update the index array with // index of corresponding // elements of B index[B[i]] = i; } var k = 0; for (i = 0; i < M; i++) { // Place only A's array values // with its mapped values // into nums array if (index[A[i]] != -1) { nums[k++] = index[A[i]]; } } // Find LCS var lcs_length = findLCS(nums, k); // No of elements to be added // in array A var elements_to_be_added = N - lcs_length; // Stores minimum cost var min_cost = elements_to_be_added * C; // Print the minimum cost document.write(min_cost); return 0; } // Driver code // Given array A var A = [ 1, 6, 3, 5, 10 ]; var B = [ 3, 1, 5 ]; // Given C var C = 2; // Size of arr A var M = A.length; // Size of arr B var N = B.length; // Function call minimumCost(A, B, M, N, C);// This code contributed by umadevi9616 </script> |
Output:
2
Time Complexity: O(N * Log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
