Minimize count of array elements to be removed such that at least K elements are equal to their index values | Function to minimize the removals of array elements such that atleast K elements are equal to their indices ; Store the array as 1 - based indexing Copy of first array ; Make a dp - table of ( N * N ) size ; Delete the current element ; Take the current element ; Check for the minimum removals ; Driver Code
def MinimumRemovals ( a , N , K ) : NEW_LINE INDENT b = [ 0 for i in range ( N + 1 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT b [ i + 1 ] = a [ i ] NEW_LINE DEDENT dp = [ [ 0 for i in range ( N + 1 ) ] for j in range ( N + 1 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( i + 1 ) : NEW_LINE INDENT dp [ i + 1 ] [ j ] = max ( dp [ i + 1 ] [ j ] , dp [ i ] [ j ] ) NEW_LINE dp [ i + 1 ] [ j + 1 ] = max ( dp [ i + 1 ] [ j + 1 ] , dp [ i ] [ j ] + ( 1 if ( b [ i + 1 ] == j + 1 ) else 0 ) ) NEW_LINE DEDENT DEDENT j = N NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT if ( dp [ N ] [ j ] >= K ) : NEW_LINE INDENT return ( N - j ) NEW_LINE DEDENT j -= 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 1 , 3 , 2 , 3 ] NEW_LINE K = 2 NEW_LINE N = len ( arr ) NEW_LINE print ( MinimumRemovals ( arr , N , K ) ) NEW_LINE DEDENT