ChangeMachine

SRM 94 · 2002-06-01 · by brett1479

Class Name: ChangeMachine

Return Type: int

Method Name: minCoins

Arg Types: (vector<int>, int)

Problem Statement

Some cash registers have change machines attached to them that automatically dispense the appropriate amount of change after a transaction, using the fewest coins possible. Additionally, different monetary systems have different sets of coin values that they may give as change, so stores that accept multiple types of currency must be able to determine how to make change under any system.

Create a class ChangeMachine that contains the method minCoins, which takes a int[] coins, whose elements represent the value of the various coins of a particular monetary system, and an int amount, and returns an int that is the minimum number of coins required to give exact change in that monetary system.

Constraints

coins will have between 0 and 10 elements, inclusive.
The elements of coins will be between 1 and 1000, inclusive.
amount will be between 0 and 1000, inclusive.

Examples

{50,25,10,5,1}
43
Returns: 6

This is the American coin system. The best answer is: 25+10+5+1+1+1 = 43, which uses 6 coins.

{50,25,10,5,1}
1000
Returns: 20

We can just give 20 coins of value 50.

{2,10,8,8}
19
Returns: -1

All of the coins have an even value and the amount is odd so change cannot be made.

{10,20,30}
0
Returns: 0

The amount is 0 so this method returns 0.

{1,2,3,4,5}
55
Returns: 11

Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChangeMachine with a public method int minCoins(vector<int> coins, int amount) · 163 test cases · 2 s / 256 MB per case