Remove minimum elements from ends of array so that sum decreases by at least K | O ( N ) | Function to return the count of minimum elements to be removed from the ends of the array such that the sum of the array decrease by at least K ; To store the final answer ; Maximum possible sum required ; Left point ; Right pointer ; Total current sum ; Two pointer loop ; If the sum fits ; Update the answer ; Update the total sum ; Increment the left pointer ; Driver code
def minCount ( arr , n , k ) : NEW_LINE INDENT ans = 0 ; NEW_LINE sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE DEDENT sum -= k ; NEW_LINE l = 0 ; NEW_LINE r = 0 ; NEW_LINE tot = 0 ; NEW_LINE while ( l < n ) : NEW_LINE INDENT if ( tot <= sum ) : NEW_LINE INDENT ans = max ( ans , r - l ) ; NEW_LINE if ( r == n ) : NEW_LINE INDENT break ; NEW_LINE DEDENT tot += arr [ r ] ; NEW_LINE r += 1 NEW_LINE DEDENT else : NEW_LINE INDENT tot -= arr [ l ] ; NEW_LINE l += 1 NEW_LINE DEDENT DEDENT return ( n - ans ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 11 , 5 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE k = 11 ; NEW_LINE print ( minCount ( arr , n , k ) ) ; NEW_LINE DEDENT