Count of minimum reductions required to get the required sum K | Python3 program to find the count of minimum reductions required to get the required sum K ; Function to return the count of minimum reductions ; If the sum is already less than K ; Sort in non - increasing order of difference ; Driver Code ; Function Call
from typing import Any , List NEW_LINE def countReductions ( v : List [ Any ] , K : int ) -> int : NEW_LINE INDENT sum = 0 NEW_LINE for i in v : NEW_LINE INDENT sum += i [ 0 ] NEW_LINE DEDENT if ( sum <= K ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT v . sort ( key = lambda a : a [ 0 ] - a [ 1 ] ) NEW_LINE i = 0 NEW_LINE while ( sum > K and i < len ( v ) ) : NEW_LINE INDENT sum -= ( v [ i ] [ 0 ] - v [ i ] [ 1 ] ) NEW_LINE i += 1 NEW_LINE DEDENT if ( sum <= K ) : NEW_LINE INDENT return i NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 NEW_LINE K = 25 NEW_LINE v = [ [ 0 , 0 ] for _ in range ( N ) ] NEW_LINE v [ 0 ] = [ 10 , 5 ] NEW_LINE v [ 1 ] = [ 20 , 9 ] NEW_LINE v [ 2 ] = [ 12 , 10 ] NEW_LINE v [ 3 ] = [ 4 , 2 ] NEW_LINE print ( countReductions ( v , K ) ) NEW_LINE DEDENT