Minimum count of elements that sums to a given number | Python3 implementation of the above approach ; we will only store min counts of sum upto 100 ; memo [ 0 ] = 0 as 0 is made from 0 elements ; fill memo array with min counts of elements that will constitute sum upto 100 ; min_count will store min count of elements chosen ; starting from end iterate over each 2 digits and add min count of elements to min_count ; Driver code
def minCount ( K ) : NEW_LINE INDENT memo = [ 10 ** 9 for i in range ( 100 ) ] NEW_LINE memo [ 0 ] = 0 NEW_LINE for i in range ( 1 , 100 ) : NEW_LINE INDENT memo [ i ] = min ( memo [ i - 1 ] + 1 , memo [ i ] ) NEW_LINE DEDENT for i in range ( 10 , 100 ) : NEW_LINE INDENT memo [ i ] = min ( memo [ i - 10 ] + 1 , memo [ i ] ) NEW_LINE DEDENT for i in range ( 25 , 100 ) : NEW_LINE INDENT memo [ i ] = min ( memo [ i - 25 ] + 1 , memo [ i ] ) NEW_LINE DEDENT min_count = 0 NEW_LINE while ( K > 0 ) : NEW_LINE INDENT min_count += memo [ K % 100 ] NEW_LINE K //= 100 NEW_LINE DEDENT return min_count NEW_LINE DEDENT K = 69 NEW_LINE print ( minCount ( K ) ) NEW_LINE