Given an array A[] consisting of N distinct integers and another array B[] consisting of M integers, the task is to find the minimum number of elements to be added to the array B[] such that the array A[] becomes the subsequence of the array B[].
Examples:
Input: N = 5, M = 6, A[] = {1, 2, 3, 4, 5}, B[] = {2, 5, 6, 4, 9, 12}
Output: 3
Explanation:
Below are the element that are needed to be added:
1) Add 1 before element 2 of B[]
2) Add 3 after element 6 of B[]
3) Add 5 in the last position of B[].
Therefore, the resulting array B[] is {1, 2, 5, 6, 3, 4, 9, 12, 5}.
Hence, A[] is the subsequence of B[] after adding 3 elements.Input: N = 5, M = 5, A[] = {3, 4, 5, 2, 7}, B[] = {3, 4, 7, 9, 2}
Output: 2
Explanation:
Below are the elements that are needed to be added:
1) Add 5 after element 4.
2) Add 2 after element 5.
Therefore, the resulting array B[] is {3, 4, 5, 2, 7, 9, 2}.
Hence 2 elements are required to be added.
Naive Approach: The naive approach is to generate all the subsequences of the array B and then find that subsequence such that on adding a minimum number of elements from the array A to make it equal to the array A. Print the minimum count of element added.
Time Complexity: O(N*2M)
Auxiliary Space: O(M+N)
Efficient Approach: The above approach can be optimized using Dynamic Programming. The idea is to find the Longest Common Subsequence between the given two arrays A and B. The main observation is that the minimum number of elements to be added in B[] such that A[] becomes its subsequence can be found by subtracting the length of the longest common subsequence from the length of the array A[].
Therefore, the difference between the length of the array A[] and length of the Longest Common Subsequence is the required result.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the minimum number// of the element must be added to make A// as a subsequence in Bint transformSubsequence(int n, int m, vector<int> A, vector<int> B){ // Base Case if (B.size() == 0) return n; // dp[i][j] indicates the length of // LCS of A of length i & B of length j vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for(int i = 0; i < n + 1; i++) { for(int j = 0; j < m + 1; j++) { // If there are no elements // either in A or B then the // length of lcs is 0 if (i == 0 or j == 0) dp[i][j] = 0; // If the element present at // ith and jth index of A and B // are equal then include in LCS else if (A[i - 1] == B[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; // If they are not equal then // take the max else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } // Return difference of length // of A and lcs of A and B return n - dp[n][m];}// Driver Codeint main(){ int N = 5; int M = 6; // Given sequence A and B vector<int> A = { 1, 2, 3, 4, 5 }; vector<int> B = { 2, 5, 6, 4, 9, 12 }; // Function call cout << transformSubsequence(N, M, A, B); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for // the above approachimport java.util.*;class GFG{// Function that finds the minimum number// of the element must be added to make A// as a subsequence in Bstatic int transformSubsequence(int n, int m, int []A, int []B){ // Base Case if (B.length == 0) return n; // dp[i][j] indicates the length of // LCS of A of length i & B of length j int [][]dp = new int[n + 1][m + 1]; for(int i = 0; i < n + 1; i++) { for(int j = 0; j < m + 1; j++) { // If there are no elements // either in A or B then the // length of lcs is 0 if (i == 0 || j == 0) dp[i][j] = 0; // If the element present at // ith and jth index of A and B // are equal then include in LCS else if (A[i - 1] == B[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; // If they are not equal then // take the max else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } // Return difference of length // of A and lcs of A and B return n - dp[n][m];}// Driver Codepublic static void main(String[] args){ int N = 5; int M = 6; // Given sequence A and B int []A = {1, 2, 3, 4, 5}; int []B = {2, 5, 6, 4, 9, 12}; // Function call System.out.print(transformSubsequence(N, M, A, B));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function that finds the minimum number# of the element must be added to make A# as a subsequence in Bdef transformSubsequence(n, m, A, B): # Base Case if B is None or len(B) == 0: return n # dp[i][j] indicates the length of # LCS of A of length i & B of length j dp = [[0 for col in range(m + 1)] for row in range(n + 1)] for i in range(n + 1): for j in range(m + 1): # If there are no elements # either in A or B then the # length of lcs is 0 if i == 0 or j == 0: dp[i][j] = 0 # If the element present at # ith and jth index of A and B # are equal then include in LCS elif A[i-1] == B[j-1]: dp[i][j] = 1 + dp[i-1][j-1] # If they are not equal then # take the max else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # Return difference of length # of A and lcs of A and B return n - dp[n][m]# Driver Codeif __name__ == "__main__": N = 5 M = 6 # Given Sequence A and B A = [1, 2, 3, 4, 5] B = [2, 5, 6, 4, 9, 12] # Function Call print(transformSubsequence(N, M, A, B)) |
C#
// C# program for // the above approachusing System;class GFG{// Function that finds the minimum number// of the element must be added to make A// as a subsequence in Bstatic int transformSubsequence(int n, int m, int []A, int []B){ // Base Case if (B.Length == 0) return n; // dp[i,j] indicates the length of // LCS of A of length i & B of length j int [,]dp = new int[n + 1, m + 1]; for(int i = 0; i < n + 1; i++) { for(int j = 0; j < m + 1; j++) { // If there are no elements // either in A or B then the // length of lcs is 0 if (i == 0 || j == 0) dp[i, j] = 0; // If the element present at // ith and jth index of A and B // are equal then include in LCS else if (A[i - 1] == B[j - 1]) dp[i, j] = 1 + dp[i - 1, j - 1]; // If they are not equal then // take the max else dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]); } } // Return difference of length // of A and lcs of A and B return n - dp[n, m];}// Driver Codepublic static void Main(String[] args){ int N = 5; int M = 6; // Given sequence A and B int []A = {1, 2, 3, 4, 5}; int []B = {2, 5, 6, 4, 9, 12}; // Function call Console.Write(transformSubsequence(N, M, A, B));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach// Function that finds the minimum number// of the element must be added to make A// as a subsequence in Bfunction transformSubsequence(n, m, A, B){ // Base Case if (B.length == 0) return n; // dp[i][j] indicates the length of // LCS of A of length i & B of length j var dp = Array.from(Array(n+1), ()=>Array(m+1).fill(0)); for(var i = 0; i < n + 1; i++) { for(var j = 0; j < m + 1; j++) { // If there are no elements // either in A or B then the // length of lcs is 0 if (i == 0 || j == 0) dp[i][j] = 0; // If the element present at // ith and jth index of A and B // are equal then include in LCS else if (A[i - 1] == B[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; // If they are not equal then // take the max else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } // Return difference of length // of A and lcs of A and B return n - dp[n][m];}// Driver Codevar N = 5;var M = 6;// Given sequence A and Bvar A = [1, 2, 3, 4, 5 ];var B = [2, 5, 6, 4, 9, 12 ];// Function calldocument.write( transformSubsequence(N, M, A, B));</script> |
Output:
3
Time Complexity: O(M*M), where N and M are the lengths of array A[] and B[] respectively.
Auxiliary Space: O(M*N)
Efficient approach : Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use a 1D vectors dp to store previous value and use prev to store the previous diagonal element and get the current computation.
Implementation Steps:
- Define a vector dp of size m+1 and initialize its first element to 0.
- For each element j in B, iterate in reverse order from n to 1 and update dp[i] as follows:
a. If A[i-1] == B[j-1], set dp[i] to the previous value of dp[i-1] (diagonal element).
b. If A[i-1] != B[j-1], set dp[i] to the maximum value between dp[i] and dp[i-1]+1 (value on the left). - Finally, return n – dp[m].
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function that finds the minimum number// of the element must be added to make A// as a subsequence in Bint transformSubsequence(int n, int m, vector<int> A, vector<int> B){ // Base Case if (B.size() == 0) return n; // dp[j] indicates the length of // LCS of A and B of length j vector<int> dp(m + 1, 0); for(int i = 1; i < n + 1; i++) { int prev = dp[0]; for(int j = 1; j < m + 1; j++) { // If the element present at // ith and jth index of A and B // are equal then include in LCS int curr = dp[j]; if (A[i - 1] == B[j - 1]) dp[j] = 1 + prev; // If they are not equal then // take the max else dp[j] = max(dp[j], dp[j - 1]); prev = curr; } } // Return difference of length // of A and lcs of A and B return n - dp[m];}// Driver Codeint main(){ int N = 5; int M = 6; // Given sequence A and B vector<int> A = { 1, 2, 3, 4, 5 }; vector<int> B = { 2, 5, 6, 4, 9, 12 }; // Function call cout << transformSubsequence(N, M, A, B); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class MinimumAdditions { // Function that finds the minimum number // of the element must be added to make A // as a subsequence in B public static int transformSubsequence(int n, int m, List<Integer> A, List<Integer> B) { // Base Case if (B.size() == 0) return n; // dp[j] indicates the length of // LCS of A and B of length j int[] dp = new int[m + 1]; for(int i = 1; i < n + 1; i++) { int prev = dp[0]; for(int j = 1; j < m + 1; j++) { // If the element present at // ith and jth index of A and B // are equal then include in LCS int curr = dp[j]; if (A.get(i - 1).equals(B.get(j - 1))) dp[j] = 1 + prev; // If they are not equal then // take the max else dp[j] = Math.max(dp[j], dp[j - 1]); prev = curr; } } // Return difference of length // of A and lcs of A and B return n - dp[m]; } // Driver Code public static void main(String[] args) { int N = 5; int M = 6; // Given sequence A and B List<Integer> A = Arrays.asList(1, 2, 3, 4, 5); List<Integer> B = Arrays.asList(2, 5, 6, 4, 9, 12); // Function call System.out.println(transformSubsequence(N, M, A, B)); }} |
Python3
# Python program for above approach# Function that finds the minimum number# of the element must be added to make A# as a subsequence in Bdef transformSubsequence(n, m, A, B): # Base Case if len(B) == 0: return n # dp[j] indicates the length of # LCS of A and B of length j dp = [0] * (m + 1) for i in range(1, n + 1): prev = dp[0] for j in range(1, m + 1): # If the element present at # ith and jth index of A and B # are equal then include in LCS curr = dp[j] if A[i - 1] == B[j - 1]: dp[j] = 1 + prev # If they are not equal then # take the max else: dp[j] = max(dp[j], dp[j - 1]) prev = curr # Return difference of length # of A and lcs of A and B return n - dp[m]# Driver Codeif __name__ == '__main__': N = 5 M = 6 # Given sequence A and B A = [1, 2, 3, 4, 5] B = [2, 5, 6, 4, 9, 12] # Function call print(transformSubsequence(N, M, A, B)) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static int TransformSubsequence(int n, int m, List<int> A, List<int> B) { // Base Case if (B.Count == 0) return n; // dp[j] indicates the length of // LCS of A and B of length j var dp = new int[m + 1]; for (int i = 1; i < n + 1; i++) { int prev = dp[0]; for (int j = 1; j < m + 1; j++) { // If the element present at // ith and jth index of A and B // are equal then include in LCS int curr = dp[j]; if (A[i - 1] == B[j - 1]) dp[j] = 1 + prev; // If they are not equal then // take the max else dp[j] = Math.Max(dp[j], dp[j - 1]); prev = curr; } } // Return difference of length // of A and lcs of A and B return n - dp[m]; } static void Main(string[] args) { int N = 5; int M = 6; // Given sequence A and B var A = new List<int> { 1, 2, 3, 4, 5 }; var B = new List<int> { 2, 5, 6, 4, 9, 12 }; // Function call Console.WriteLine(TransformSubsequence(N, M, A, B)); }} |
Javascript
// Define a function that finds the minimum number// of the element must be added to make A as a subsequence in Bfunction transformSubsequence(n, m, A, B) { // Base Case: if B is an empty list, then all elements of A // need to be added to B to make A a subsequence of Bif (B.length === 0) return n;// Define a dynamic programming array dp of length m+1 // where dp[j] indicates the length of the longest common subsequence (LCS) // of A and B of length jlet dp = new Array(m + 1).fill(0);// Loop through the elements of Afor(let i = 1; i < n + 1; i++) { // Define a variable prev to keep track of the value of dp[j-1] // in the previous iteration let prev = dp[0]; // Loop through the elements of B for(let j = 1; j < m + 1; j++) { // Define a variable curr to keep track of the value of dp[j] // in the previous iteration let curr = dp[j]; // If the ith element of A is equal to the jth element of B, // include this element in the LCS if (A[i - 1] === B[j - 1]) dp[j] = 1 + prev; // If the ith element of A is not equal to the jth element of B, // then take the maximum of dp[j] and dp[j-1] to find the // longest common subsequence so far else dp[j] = Math.max(dp[j], dp[j - 1]); // Update prev with the value of curr for the next iteration prev = curr; }}// Return the difference of the length of A and the LCS of A and B, which is the minimum number of elements that must be added to B to make A a subsequence of Breturn n - dp[m];}// Test the function with the given inputlet N = 5;let M = 6;let A = [1, 2, 3, 4, 5];let B = [2, 5, 6, 4, 9, 12];console.log(transformSubsequence(N, M, A, B)); |
Output
3
Time Complexity: O(M*M), where N and M are the lengths of array A[] and B[] respectively.
Auxiliary Space: O(M)
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!
