Minimize elements to be added to a given array such that it contains another given array as its subsequence | Set 2 | C ++ program for the above approach ; Function to return minimum element to be added in array B so that array A become subsequence of array B ; Stores indices of the array elements ; Iterate over the array ; Store the indices of the array elements ; Stores the LIS ; Check if element B [ i ] is in array A [ ] ; Perform Binary Search ; Find the value of mid m ; Update l and r ; If found better element ' e ' for pos r + 1 ; Otherwise , extend the current subsequence ; Return the answer ; Driver code ; Given arrays ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minElements ( int A [ ] , int B [ ] , int N , int M ) { map < int , int > map ; for ( int i = 0 ; i < N ; i ++ ) { map [ A [ i ] ] = i ; } vector < int > subseq ; int l = 0 , r = -1 ; for ( int i = 0 ; i < M ; i ++ ) { if ( map . find ( B [ i ] ) != map . end ( ) ) { int e = map [ B [ i ] ] ; while ( l <= r ) { int m = l + ( r - l ) / 2 ; if ( subseq [ m ] < e ) l = m + 1 ; else r = m - 1 ; } if ( r + 1 < subseq . size ( ) ) { subseq [ r + 1 ] = e ; } else { subseq . push_back ( e ) ; } l = 0 ; r = subseq . size ( ) - 1 ; } } return N - subseq . size ( ) ; } int main ( ) { int A [ ] = { 1 , 2 , 3 , 4 , 5 } ; int B [ ] = { 2 , 5 , 6 , 4 , 9 , 12 } ; int M = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int N = sizeof ( B ) / sizeof ( B [ 0 ] ) ; cout << minElements ( A , B , M , N ) ; return 0 ; }