Remove minimum elements from either side such that 2 * min becomes more than max | C ++ implementation of above approach ; A utility function to find minimum of two numbers ; A utility function to find minimum in arr [ l . . h ] ; A utility function to find maximum in arr [ l . . h ] ; Returns the minimum number of removals from either end in arr [ l . . h ] so that 2 * min becomes greater than max . ; If there is 1 or less elements , return 0 For a single element , 2 * min > max ( Assumption : All elements are positive in arr [ ] ) ; 1 ) Find minimum and maximum in arr [ l . . h ] ; If the property is followed , no removals needed ; Otherwise remove a character from left end and recur , then remove a character from right end and recur , take the minimum of two is returned ; Driver program to test above functions
#include <iostream> NEW_LINE using namespace std ; int min ( int a , int b ) { return ( a < b ) ? a : b ; } int min ( int arr [ ] , int l , int h ) { int mn = arr [ l ] ; for ( int i = l + 1 ; i <= h ; i ++ ) if ( mn > arr [ i ] ) mn = arr [ i ] ; return mn ; } int max ( int arr [ ] , int l , int h ) { int mx = arr [ l ] ; for ( int i = l + 1 ; i <= h ; i ++ ) if ( mx < arr [ i ] ) mx = arr [ i ] ; return mx ; } int minRemovals ( int arr [ ] , int l , int h ) { if ( l >= h ) return 0 ; int mn = min ( arr , l , h ) ; int mx = max ( arr , l , h ) ; if ( 2 * mn > mx ) return 0 ; return min ( minRemovals ( arr , l + 1 , h ) , minRemovals ( arr , l , h - 1 ) ) + 1 ; } int main ( ) { int arr [ ] = { 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minRemovals ( arr , 0 , n - 1 ) ; return 0 ; }