Minimum removals from array to make max | PHP 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
< ? php $ MAX = 100 ; $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ MAX ; $ i ++ ) { for ( $ j = 0 ; $ j < $ MAX ; $ j ++ ) $ dp [ $ i ] [ $ j ] = -1 ; } function countRemovals ( $ a , $ i , $ j , $ k ) { global $ dp ; 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 + min ( countRemovals ( $ a , $ i + 1 , $ j , $ k ) , countRemovals ( $ a , $ i , $ j - 1 , $ k ) ) ; } return $ dp [ $ i ] [ $ j ] ; } function removals ( $ a , $ n , $ k ) { sort ( $ a ) ; if ( $ n == 1 ) return 0 ; else return countRemovals ( $ a , 0 , $ n - 1 , $ k ) ; } $ a = array ( 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 ) ; $ n = count ( $ a ) ; $ k = 4 ; echo ( removals ( $ a , $ n , $ k ) ) ; ? >