Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Making Change by asaka.
def checkio(price, denominations):
c = max(denominations)
stuck = [(i,c*i,c) for i in range((price//c)+1)]
num = price // min(denominations)
flag = 0
while stuck:
p = stuck.pop()
left = price - p[1]
m = max(x for x in denominations if x not in p[2:])
if left%m == 0:
if p[0]+(left//m) < num:
num = p[0]+(left//m)
flag += 1
else:
continue
elif p[0]+(left//m) < num:
for n in range((left//m)+1):
tp = (p[0]+n, p[1]+n*m, m) + p[2:]
stuck.append(tp)
return num if flag > 0 else None
if __name__ == '__main__':
print("Example:")
print(checkio(8, [1, 3, 5]))
#These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio(8, [1, 3, 5]) == 2
assert checkio(12, [1, 4, 5]) == 3
print('Done')
May 3, 2021
Comments:
