Vending Machines

Computer Science Level 2

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.

90 120 150 210

1 solution

Judy Gu
Mar 5, 2017

Algorithm: 120 = 50 + 50 + 10 + 10

Alternative with fewer coins: 120 = 40 + 40 + 40

Since the algorithm requires that the denomination always be smaller than the remaining amount, all of the change will never be returned and all answers are correct. Had the algorithm stated "the largest denominator equal to or less than the remaining amount," 120 would be the correct answer.

D Rogers - 4 years, 3 months ago

Thanks. I've made that corresponding edit. Note that if we're forced to always use "denomination that is strictly smaller than the remaining amount", then this algorithm would never end.

Calvin Lin Staff - 4 years, 3 months ago

The problem is not updated.

Jeannine Myer - 4 years, 3 months ago

Thanks. I've updated the options accordingly.

Calvin Lin Staff - 4 years, 3 months ago

The proposition of the problem is very vague and convoluted!

Mahabubul Islam - 4 years, 3 months ago

Which part do you find vague/convoluted?

How do you think it can be improved on?

Pi Han Goh - 4 years, 3 months ago

50+40 had fewer coins than 40+40+40. Why is 90 not the answer?

Esosa Uhunmwarabona - 4 years, 3 months ago

I think you are interpreting the question as "Which amount requires the smallest number of coins?" in which case the answer would be 90, because it only requires 2 coins.

However, the question asks for the amount for which the described algorithm does not give optimal results. Out of the given choices, only 120 does not give optimal results, as shown by Judy in the solution. The algorithm returns 4 coins, but it is possible to make 120 with just 3 coins.

Pranshu Gaba - 4 years, 3 months ago

why can't it be 150? 50,50,50 ...

or 50+50+10+10+10+10+10

Martine Suid Jaffe - 4 years, 3 months ago

Because the question asks for an amount that could return FEWER coins than the algorithm calls for.

Avery Bentley Sollmann - 4 years, 3 months ago

Why is not 90 the answer? I don't find it clear enough.

Irina Stanciu - 4 years, 3 months ago

For 90, the vending machine gives you 50 and 40. Can you do better than that?

Agnishom Chattopadhyay - 4 years, 3 months ago

As there are many confusions about your problem's text I think you should explain it better so that everybody else would be able to do better than that.

Irina Stanciu - 4 years, 2 months ago

Why is 90 not an answer?

Algorithm: 50 + 10 + 10 + 10 + 10 Alternative: 50 + 40

Soumil Sahu - 3 years, 7 months ago

The algorithm also gives 50 + 40. Why would the algorithm give 50 + 10 + 10 + 10 + 10?

Pranshu Gaba - 3 years, 7 months ago

Ah I see, I misunderstood the question because of the diagram. I thought that initially, the machine can only give out 50 and 10 cents and 40 is added later. Turns out that 40 was part of the original algorithm.

Soumil Sahu - 3 years, 7 months ago

@Soumil Sahu – It's alright. The image illustrates the example where it has to give 110 cents as change.

Pranshu Gaba - 3 years, 7 months ago

Could it be clearer (maybe in the example) that 40 cents is a coin denomination? Since we don't have 40-cent coins in the US and I was being ethnocentric, I had to think more about what "the denominations 10, 40, and 50 cents," meant in order for me to come up with the right answer since I was just assuming half-dollars, quarters, dimes, and nickels.

Avery Bentley Sollmann - 4 years, 3 months ago

This. I suppose there exists a 40¢ denomination in many parts of the world, such as Malaysia (the author's home). However, the dead giveaway was the problem's mention of a 50¢ coin (a rarity in the US). I guess this is a good incentive to knowing international currencies!

Michael Fitzgerald - 4 years, 3 months ago

40 cents is not a coin denomination in Malaysia either xD. It was being set this way for the purpose of this problem.

Christopher Boo - 4 years, 2 months ago

@Christopher Boo – Like when math problems say "You can only buy watermelons in batches of 5 or 7 ..."

Calvin Lin Staff - 4 years, 2 months ago

Vending Machines

1 solution

0 pending reports