Minimum removals from array to make max | JavaScript 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
let MAX = 100 ; let dp = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { dp [ i ] = new Array ( MAX ) ; } function countRemovals ( a , i , j , 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 ] ; } function removals ( a , n , k ) { a . sort ( function ( a , b ) { return a - b } ) ; for ( let i = 0 ; i < MAX ; i ++ ) { for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } if ( n == 1 ) return 0 ; else return countRemovals ( a , 0 , n - 1 , k ) ; } let a = [ 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 ] ; let n = a . length ; let k = 4 ; document . write ( removals ( a , n , k ) ) ;