Minimize count of array elements to be removed such that at least K elements are equal to their index values | C ++ program 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 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MinimumRemovals ( int a [ ] , int N , int K ) { int b [ N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { b [ i + 1 ] = a [ i ] ; } int dp [ N + 1 ] [ N + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j <= i ; j ++ ) { dp [ i + 1 ] [ j ] = max ( dp [ i + 1 ] [ j ] , dp [ i ] [ j ] ) ; dp [ i + 1 ] [ j + 1 ] = 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 ; } int main ( ) { int arr [ ] = { 5 , 1 , 3 , 2 , 3 } ; int K = 2 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << MinimumRemovals ( arr , N , K ) ; return 0 ; }