Minimum removals from array to make max | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100 NEW_LINE int dp [ MAX ] [ MAX ] ; 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 + min ( countRemovals ( a , i + 1 , j , k ) , countRemovals ( a , i , j - 1 , k ) ) ; } return dp [ i ] [ j ] ; } int removals ( int a [ ] , int n , int k ) { sort ( a , a + n ) ; memset ( dp , -1 , sizeof ( dp ) ) ; if ( n == 1 ) return 0 ; else return countRemovals ( a , 0 , n - 1 , k ) ; } int main ( ) { int a [ ] = { 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 4 ; cout << removals ( a , n , k ) ; return 0 ; }