Shopping | Topcoder Archive

Problem Statement

Christmas is coming soon and you still have so many things to buy. You are going to the store and don't expect to spend more than X dollars. You want to be able to pay any integer amount not exceeding X dollars, and you want to take as few coins as possible to achieve this.

You are given a int[] values, each element of which describes the dollar value of a kind of coin. You have an unlimited supply of each kind of coin. Return the minimal number of coins you need to take, or -1 if it is impossible to achieve your goal.

Definition

Class:: Shopping
Method:: minNumber
Parameters:: int, int[]
Returns:: int
Method signature:: int minNumber(int X, int[] values)
(be sure your method is public)

Constraints

X will be between 1 and 1000, inclusive.
values will contain between 1 and 10 elements, inclusive.
Each element of values will be between 1 and 1000, inclusive.
The elements in values will be distinct.

Examples

```
20
```
```
{1, 2, 5, 10}
```
```
Returns: 5
```
Taking 5 coins with values {1,2,2,5,10} allows you to pay any integer amount between 1 and 20, inclusive.
```
7
```
```
{2, 4, 1, 7}
```
```
Returns: 3
```
Here, taking {2,4,1} is enough.
```
20
```
```
{2,4,6,8}
```
```
Returns: -1
```
These nominals allow you to pay only even amounts.
```
600
```
```
{1,2,3,10,11,30}
```
```
Returns: 25
```

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.