Python вопросы с собеседований

📌 Задача



У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500).

Покупатель купил товар на сумму n. Hужно найти

минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец.



Решение

a = input('Введите сумму: ')



d = dict.fromkeys([500, 200, 100, 50, 20, 10, 5, 2, 1], 0)



def get_nearest_value(iterable, value):

return min(iterable, key=lambda x: abs(x - value))



for i in d.keys():

d[i] = _i = int(a)/i

a = int(a)%i



_key = get_nearest_value(d.keys(), a)

d[_key] += 1



for k in d.keys():

print('%s - %d' % (k, d[k]))



Какая временная сложность данного алгоритма?



👉 Пишите ваше решение в комментариях👇



@python_job_interview