1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#!/usr/bin/env python
def isExactChangePossible(bills):
till = {}; # we keep the bills in a "till"
for collected in bills:
# put the bill we collected in the "till"
#
# using .get(collected, 0) yields the value in the
# dict for the key 'collected' if it exists, or the
# specified default (in this case, 0) if it doesn't
till[collected] = till.get(collected, 0) + 1
# calculate the required change
change_required = collected - 5
# loop through the bills we have on hand
for bill in sorted(till, reverse=True):
# as long as we have more of this bill and
# using it would not yield TOO MUCH change
while till[bill] > 0 and change_required - bill >= 0:
# deduct the amount from the required change
change_required -= bill
# remove the bill from the till
till[bill] -= 1
# if we weren't able to make change, fail
if change_required:
return 0
# we successfully made change for all transactions!
return 1
def solution(bills):
as_list = ', '.join(map(lambda i: str(i), bills))
print(f'Input: @bills = ({as_list})')
output = isExactChangePossible(bills)
print(f'Output: {"true" if output else "false"}')
print('Example 1:')
solution([5, 5, 5, 10, 20])
print('\nExample 2:')
solution([5, 5, 10, 10, 20])
print('\nExample 3:')
solution([5, 5, 5, 20])
|
