TopCoder Statistics - Problem Statement

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,2,3,4,5,6,7,8,9,10}

1000

Returns: 100
{1,1,1,1,1,1,1,1,1,1}

1000

Returns: 1000
{3,8}

12

Returns: 4
{1,2,4,8,16,32,64,128,256,512}

987

Returns: 8
{54,23,423,89,123,90,123,42}

22

Returns: -1
{1,2,3,4,5,6,7,8,9,10}

8

Returns: 1
{1,2,3,4,5,6,7,8,9,10}

0

Returns: 0
{10,50,100,250,500,100}

990

Returns: 8
{}

0

Returns: 0
{}

5

Returns: -1
{1,20,25}

40

Returns: 2
{10,20}

0

Returns: 0
{}

10

Returns: -1
{1,2,3,4,5,6,7,8,9}

991

Returns: 111
{37,50,1,60}

111

Returns: 3
{50,30,1}

60

Returns: 2
{3,7}

29

Returns: 7
{10}

0

Returns: 0
{2,10,8,8}

19

Returns: -1
{1,20,25}

40

Returns: 2
{3,7}

29

Returns: 7
{1,1,1,4,5}

20

Returns: 4
{1,20,25}

65

Returns: 3
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{1,4,6}

8

Returns: 2
{}

0

Returns: 0
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{2,10,8,8}

16

Returns: 2
{}

0

Returns: 0
{7,3}

30

Returns: 6
{25,12,10,1}

45

Returns: 3
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{1,1,3,3,5,5,7,7,9,9}

100

Returns: 12
{}

0

Returns: 0
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{25}

28

Returns: -1
{}

0

Returns: 0
{}

0

Returns: 0
{25,12,10,1}

45

Returns: 3
{50,21,10,1}

63

Returns: 3
{30,25,10}

50

Returns: 2
{1,14,25}

28

Returns: 2
{}

0

Returns: 0
{1,7,11}

14

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{15,11,1}

22

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{1,5,23}

45

Returns: 7
{501,500,8,7,6,5,4,3,2,1}

1000

Returns: 2
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{1,20,25}

65

Returns: 3
{1,1,1,20,25}

43

Returns: 5
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{}

1

Returns: -1
{1,20,25}

40

Returns: 2
{}

54

Returns: -1
{1,7,11}

14

Returns: 2
{50,50,50,50,50,50,50,30,1}

60

Returns: 2
{2,7,10}

14

Returns: 2
{25,12,10,5,1}

15

Returns: 2
{50,30,1}

60

Returns: 2
{}

0

Returns: 0
{10,7,5,2}

14

Returns: 2
{1,2,3,4,5,6,7,8,9,10}

10

Returns: 1
{7,3}

30

Returns: 6
{1,7,11}

14

Returns: 2
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{}

0

Returns: 0
{5,3}

9

Returns: 3
{7,3}

30

Returns: 6
{1,20,25}

40

Returns: 2
{2,10,8,8}

19

Returns: -1
{1,20,25}

40

Returns: 2
{}

17

Returns: -1
{1,7,11}

14

Returns: 2
{}

10

Returns: -1
{1,20,25}

40

Returns: 2
{25,12,10,1}

45

Returns: 3
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{7,3}

30

Returns: 6
{20,7,1}

28

Returns: 3
{1,1,1,1,1,1,1,1,1,1}

1000

Returns: 1000
{1,7,11}

14

Returns: 2
{}

0

Returns: 0
{2,5,9,10}

14

Returns: 2
{10,9,8}

17

Returns: 2
{1,20,25}

60

Returns: 3
{5}

4

Returns: -1
{7,3}

30

Returns: 6
{1}

1

Returns: 1
{}

10

Returns: -1
{2,2}

5

Returns: -1
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{2,10,8,8}

16

Returns: 2
{}

0

Returns: 0
{1}

1000

Returns: 1000
{1,20,25}

41

Returns: 3
{20}

1000

Returns: 50
{10,9,8}

17

Returns: 2
{1,20,25}

40

Returns: 2
{6,19,20}

25

Returns: 2
{}

5

Returns: -1
{}

10

Returns: -1
{1,4,6}

8

Returns: 2
{50,21,10,1}

63

Returns: 3
{}

0

Returns: 0
{}

10

Returns: -1
{10,9,8,7,6,5,4,3,2,1}

1000

Returns: 100
{7,5}

24

Returns: 4
{7,6,5,1}

11

Returns: 2
{1,20,25}

40

Returns: 2
{1,20,25}

40

Returns: 2
{8,9,1,5}

19

Returns: 3
{}

0

Returns: 0
{10,20,30}

0

Returns: 0
{3,2}

7

Returns: 3
{10,12,15}

37

Returns: 3
{}

0

Returns: 0
{19,2}

20

Returns: 10
{}

0

Returns: 0
{20,25}

40

Returns: 2
{25,12,10,1}

45

Returns: 3
{50,30,1}

60

Returns: 2
{10,8,5,1}

13

Returns: 2
{3,2}

7

Returns: 3
{}

0

Returns: 0
{95,40,30,1}

100

Returns: 3
{2,10,8,8}

19

Returns: -1
{1,20,25}

40

Returns: 2
{1,5,25,27,19}

38

Returns: 2
{1,20,25}

40

Returns: 2
{}

0

Returns: 0
{50,20,15,2,1}

80

Returns: 3
{2,7}

10

Returns: 5
{3,5}

9

Returns: 3
{50,21,10,1}

63

Returns: 3
{1,20,25}

40

Returns: 2
{}

10

Returns: -1

Statistics

Problem Statement for "ChangeMachine"

Problem Statement

Definition

Constraints

Examples