Minimum cost required to rearrange a given array to make it equal to another given array | Function to find lower_bound ; Function to find length of the longest common subsequence ; Find position where element is to be inserted ; Return the length of LCS ; Function to find the minimum cost required to convert the sequence A exactly same as B ; Auxiliary array ; Stores positions of elements of A [ ] Initialize index array with - 1 ; Update the index array with index of corresponding elements of B ; Place only A 's array values  with its mapped values  into nums array ; Find LCS ; No of elements to be added in array A [ ] ; Stores minimum cost ; Print the minimum cost ; Given array A [ ] ; Given C ; Size of arr A ; Size of arr B ; Function call
def LowerBound ( a , k , x ) : NEW_LINE INDENT l = - 1 NEW_LINE r = k NEW_LINE while ( l + 1 < r ) : NEW_LINE INDENT m = ( l + r ) >> 1 NEW_LINE if ( a [ m ] >= x ) : NEW_LINE INDENT r = m NEW_LINE DEDENT else : NEW_LINE INDENT l = m NEW_LINE DEDENT DEDENT return r NEW_LINE DEDENT def findLCS ( nums , N ) : NEW_LINE INDENT k = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT pos = LowerBound ( nums , k , nums [ i ] ) NEW_LINE nums [ pos ] = nums [ i ] NEW_LINE if ( k == pos ) : NEW_LINE INDENT k = pos + 1 NEW_LINE DEDENT DEDENT return k NEW_LINE DEDENT def minimumCost ( A , B , M , N , C ) : NEW_LINE INDENT nums = [ 0 ] * 100000 NEW_LINE index = [ - 1 ] * 100000 NEW_LINE for i in range ( N ) : NEW_LINE INDENT index [ B [ i ] ] = i NEW_LINE DEDENT k = 0 NEW_LINE for i in range ( M ) : NEW_LINE INDENT if ( index [ A [ i ] ] != - 1 ) : NEW_LINE INDENT k += 1 NEW_LINE nums [ k ] = index [ A [ i ] ] NEW_LINE DEDENT DEDENT lcs_length = findLCS ( nums , k ) NEW_LINE elements_to_be_added = N - lcs_length NEW_LINE min_cost = elements_to_be_added * C NEW_LINE print ( min_cost ) NEW_LINE DEDENT A = [ 1 , 6 , 3 , 5 , 10 ] NEW_LINE B = [ 3 , 1 , 5 ] NEW_LINE C = 2 NEW_LINE M = len ( A ) NEW_LINE N = len ( B ) NEW_LINE minimumCost ( A , B , M , N , C ) NEW_LINE