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
< ? php function min_1 ( & $ arr , $ l , $ h ) { $ mn = $ arr [ $ l ] ; for ( $ i = $ l + 1 ; $ i <= $ h ; $ i ++ ) if ( $ mn > $ arr [ $ i ] ) $ mn = $ arr [ $ i ] ; return $ mn ; } function max_1 ( & $ arr , $ l , $ h ) { $ mx = $ arr [ $ l ] ; for ( $ i = $ l + 1 ; $ i <= $ h ; $ i ++ ) if ( $ mx < $ arr [ $ i ] ) $ mx = $ arr [ $ i ] ; return $ mx ; } function minRemovals ( & $ arr , $ l , $ h ) { if ( $ l >= $ h ) return 0 ; $ mn = min_1 ( $ arr , $ l , $ h ) ; $ mx = max_1 ( $ arr , $ l , $ h ) ; if ( 2 * $ mn > $ mx ) return 0 ; return min ( minRemovals ( $ arr , $ l + 1 , $ h ) , minRemovals ( $ arr , $ l , $ h - 1 ) ) + 1 ; } $ arr = array ( 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 ) ; $ n = sizeof ( $ arr ) ; echo minRemovals ( $ arr , 0 , $ n - 1 ) ; ? >