ChangeMachine | Topcoder Archive

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.

Definition

Class:: ChangeMachine
Method:: minCoins
Parameters:: int[], int
Returns:: int
Method signature:: int minCoins(int[] coins, int amount)
(be sure your method is public)

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
```
```
{1,1,3,3,5,5,7,7,9,9}
```
```
100
```
```
Returns: 12
```
```
{1,20,25}
```
```
40
```
```
Returns: 2
```
```
{}
```
```
10
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.