Minimum removals from array to make max | Python 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
MAX = 100 NEW_LINE dp = [ [ 0 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE for i in range ( 0 , MAX ) : NEW_LINE INDENT for j in range ( 0 , MAX ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT def countRemovals ( a , i , j , k ) : NEW_LINE INDENT global dp NEW_LINE if ( i >= j ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( ( a [ j ] - a [ i ] ) <= k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT elif ( ( a [ j ] - a [ i ] ) > k ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 + min ( countRemovals ( a , i + 1 , j , k ) , countRemovals ( a , i , j - 1 , k ) ) NEW_LINE DEDENT return dp [ i ] [ j ] NEW_LINE DEDENT def removals ( a , n , k ) : NEW_LINE INDENT a . sort ( ) NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return countRemovals ( a , 0 , n - 1 , k ) NEW_LINE DEDENT DEDENT a = [ 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 ] NEW_LINE n = len ( a ) NEW_LINE k = 4 NEW_LINE print ( removals ( a , n , k ) ) NEW_LINE