TheCoinsProblem | Topcoder Archive

Problem Statement

There is a classical problem called the Coins Problem. It consist of a list of coins values, and asks about the various ways to make exactly n cents using those denominations (for some n).

One method to do this is to always take the biggest coin possible. For instance, with coin values of 1, 7 and 10, if we want to make 15 cents, we would first take a 10, as it's the biggest possible coin we can take. We would then have to take five 1 cent coins to complete our 15 cents. (Note that for this case, we do not care about how many coins are used, only that it is possible.)

However, this procedure--known as the greedy method--doesn't always work. For example, if you have coins of 2 and 3 cents and you want to make 4 cents, it is clearly possible by taking 2 of the 2-cent coins, but the greedy method would first take a 3 cent coin, and then be unable to come up with the other cent. Of course, some values, like making 1 cent, are impossible no matter what method is chosen.

Given int[] values listing the values of your available coins, find the minimum value that can be made using those denominations, but where the greedy method would fail. If the greedy always works in every case where it is actually possible to make a given value, then return -1.

Definition

Class:: TheCoinsProblem
Method:: calculate
Parameters:: int[]
Returns:: int
Method signature:: int calculate(int[] values)
(be sure your method is public)

Notes

The values only refers to the available coin denominations. You can assume you have an indefinite supply of each value coin available.

Constraints

values will have between 1 and 50 elements inclusive.
Each element of values will be between 1 and 1000 inclusive.
All elements of values will be in strictly increasing order.

Examples

```
{1,5,10,25,50}
```
```
Returns: -1
```
You always have one cents coins so the greedy will always work.
```
{10,15}
```
```
Returns: 20
```
Obviously we can choose 10+10 to get 20. But greedy first takes 15, leaving no way to make 5 cents.
```
{1,7,10}
```
```
Returns: -1
```
This is the example from the problem statement.
```
{2,3}
```
```
Returns: 4
```
This was also covered in the problem statement.

{994,995,996,997,998,999,1000}

Returns: 1988

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.