Vending Machines

A vending machine is designed to return change in the following way:

Keep returning the coin with the largest denomination smaller than or equal to the remaining amount until all of the change has been returned.

However, this approach doesn't always yield the least number of coins. With the denominations 10, 40, and 50 cents, which of the following changes (in cents) could be returned using fewer coins than what the algorithm requires?


As an explicit example of the algorithm, when required to produce a 110 cents change, the vending machine would return the coins 50, 50, 10 cents, in that order.

×

Problem Loading...

Note Loading...

Set Loading...