Minimize count of array elements to be removed such that at least K elements are equal to their index values | C # code for the above approach ; 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 ; Code
using System ; public class GFG { static int MinimumRemovals ( int [ ] a , int N , int K ) { int [ ] b = new int [ N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { b [ i + 1 ] = a [ i ] ; } int [ , ] dp = new int [ N + 1 , N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j <= i ; j ++ ) { dp [ i + 1 , j ] = Math . Max ( dp [ i + 1 , j ] , dp [ i , j ] ) ; dp [ i + 1 , j + 1 ] = Math . Max ( dp [ i + 1 , j + 1 ] , dp [ i , j ] + ( ( b [ i + 1 ] == j + 1 ) ? 1 : 0 ) ) ; } } for ( int j = N ; j >= 0 ; j -- ) { if ( dp [ N , j ] >= K ) { return ( N - j ) ; } } return - 1 ; } static public void Main ( ) { int [ ] arr = { 5 , 1 , 3 , 2 , 3 } ; int K = 2 ; int N = arr . Length ; Console . Write ( MinimumRemovals ( arr , N , K ) ) ; } }