Remove minimum elements from either side such that 2 * min becomes more than max | 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 Code
def mini ( arr , l , h ) : NEW_LINE INDENT mn = arr [ l ] NEW_LINE for i in range ( l + 1 , h + 1 ) : NEW_LINE INDENT if ( mn > arr [ i ] ) : NEW_LINE INDENT mn = arr [ i ] NEW_LINE DEDENT DEDENT return mn NEW_LINE DEDENT def max ( arr , l , h ) : NEW_LINE INDENT mx = arr [ l ] NEW_LINE for i in range ( l + 1 , h + 1 ) : NEW_LINE INDENT if ( mx < arr [ i ] ) : NEW_LINE INDENT mx = arr [ i ] NEW_LINE DEDENT DEDENT return mx NEW_LINE DEDENT def minRemovals ( arr , l , h ) : NEW_LINE INDENT if ( l >= h ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT mn = mini ( arr , l , h ) NEW_LINE mx = max ( arr , l , h ) NEW_LINE if ( 2 * mn > mx ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( min ( minRemovals ( arr , l + 1 , h ) , minRemovals ( arr , l , h - 1 ) ) + 1 ) NEW_LINE DEDENT arr = [ 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minRemovals ( arr , 0 , n - 1 ) ) NEW_LINE