Minimum cost required to rearrange a given array to make it equal to another given array

0 0 9 minutes read

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 subsequence
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 = 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 B
int 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 Code
int 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_bound
static 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 subsequence
static 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 B
static 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 code
public 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_bound
def 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 subsequence
def 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 B
def  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 C
C = 2
  
# Size of arr A
M = len(A)
  
# Size of arr B
N = len(B)
  
# Function call
minimumCost(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_bound
static 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 subsequence
static 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 B
static 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 code
public 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:

Time Complexity: O(N * Log N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!