Minimum removals from array to make max | C # program to find minimum removals to make max - min <= K ; function to check all possible combinations of removal and return the minimum one ; base case when all elements are removed ; if condition is satisfied , no more removals are required ; if the state has already been visited ; when Amax - Amin > d ; minimum is taken of the removal of minimum element or removal of the maximum element ; To sort the array and return the answer ; sort the array ; fill all stated with - 1 when only one element ; Driver code
using System ; class GFG { static int MAX = 100 ; static int [ , ] dp = new int [ MAX , MAX ] ; static int countRemovals ( int [ ] a , int i , int j , int k ) { if ( i >= j ) return 0 ; else if ( ( a [ j ] - a [ i ] ) <= k ) return 0 ; else if ( dp [ i , j ] != - 1 ) return dp [ i , j ] ; else if ( ( a [ j ] - a [ i ] ) > k ) { dp [ i , j ] = 1 + Math . Min ( countRemovals ( a , i + 1 , j , k ) , countRemovals ( a , i , j - 1 , k ) ) ; } return dp [ i , j ] ; } static int removals ( int [ ] a , int n , int k ) { Array . Sort ( a ) ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) dp [ i , j ] = - 1 ; } if ( n == 1 ) return 0 ; else return countRemovals ( a , 0 , n - 1 , k ) ; } static void Main ( ) { int [ ] a = new int [ ] { 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 } ; int n = a . Length ; int k = 4 ; Console . Write ( removals ( a , n , k ) ) ; } }