TopCoder Statistics - Problem Statement

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

5

{1}

Returns: 5
1000

{1}

Returns: 1000
1000

{1, 2}

Returns: 501
5

{1, 2}

Returns: 3
3

{1, 2}

Returns: 2
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.
20

{1, 2, 3, 4}

Returns: 7
1

{1, 2, 3, 4}

Returns: 1
1000

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

Returns: 103
1000

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

Returns: -1
10

{3, 4, 6}

Returns: -1
1000

{1, 3, 4, 6}

Returns: 169
987

{1, 17, 181}

Returns: 31
930

{1, 5, 881}

Returns: 181
949

{1, 2, 3, 7, 9, 47, 481}

Returns: 19
222

{1, 11, 22, 33, 44, 55, 66, 77, 88, 99}

Returns: 15
20

{1, 2, 100}

Returns: 11
11

{2, 3}

Returns: -1
724

{8, 5, 29, 1, 33}

Returns: 29
874

{423, 123, 354, 1, 674}

Returns: 126
7

{2, 4, 1, 7}

Returns: 3

Here, taking {2,4,1} is enough.
919

{41, 23, 55, 27, 1}

Returns: 40
654

{88, 29, 1, 82, 79}

Returns: 37
30

{57, 1, 68, 33, 83, 7, 2}

Returns: 8
643

{17, 45, 1, 26, 10}

Returns: 25
806

{99, 70, 76, 47, 131, 1}

Returns: 53
468

{34, 73, 57, 97, 27, 1, 48, 8}

Returns: 16
768

{46, 71, 15, 1, 57}

Returns: 28
205

{11, 1, 25, 12, 46, 39}

Returns: 17
432

{90, 23, 82, 28, 50, 10, 7, 1}

Returns: 15
370

{147, 979, 1, 78, 517, 772}

Returns: 80
872

{775, 450, 835, 1}

Returns: 450
887

{432, 355, 445, 959, 22, 31, 1, 234, 563, 844}

Returns: 31
391

{916, 13, 649, 344, 873, 304, 1}

Returns: 36
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
1000

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

Returns: 10
1000

{1, 10, 100, 105 }

Returns: 27
2

{1, 1000 }

Returns: 2
10

{1, 2, 7 }

Returns: 5
10

{1, 9 }

Returns: 9
7

{1, 2, 3, 4 }

Returns: 3
5

{1, 2, 4, 8, 16, 32 }

Returns: 3
15

{1, 10 }

Returns: 10
10

{1, 100 }

Returns: 10
93

{1, 23 }

Returns: 26
11

{1, 10 }

Returns: 10
1

{1 }

Returns: 1
4

{1, 3, 4 }

Returns: 3
1

{2 }

Returns: -1
1000

{1, 990 }

Returns: 990
7

{1, 3 }

Returns: 4
600

{1 }

Returns: 600
6

{1, 2, 3, 4, 5, 6 }

Returns: 3
155

{1, 2, 10, 20, 40, 80 }

Returns: 9
60

{1, 29 }

Returns: 30
4

{1, 3 }

Returns: 3
5

{1, 2, 10 }

Returns: 3
999

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

Returns: 114
17

{1, 5, 6, 7, 8 }

Returns: 6
1000

{1 }

Returns: 1000
21

{1, 2, 5, 10 }

Returns: 6
12

{1, 2, 3, 4, 5 }

Returns: 4
1000

{1, 2, 3, 4, 7, 8, 14, 15, 31, 32 }

Returns: 36
1

{1, 5 }

Returns: 1
500

{1, 2, 4, 8, 16, 32, 64, 128, 246, 249 }

Returns: 9
30

{1, 23 }

Returns: 23
14

{1, 2, 4, 8 }

Returns: 4
997

{2, 3, 4, 5, 123, 125, 127, 1, 55, 17 }

Returns: 16
100

{2, 3, 1, 54, 34, 65, 98, 67, 128, 324 }

Returns: 14
65

{1, 35 }

Returns: 35
1000

{998, 999, 1 }

Returns: 998
1000

{1, 2, 3, 4, 7, 14, 15, 497, 999, 1000 }

Returns: 38
5

{1, 4 }

Returns: 4
27

{1, 7, 8, 14 }

Returns: 8

Statistics

Problem Statement for "Shopping"

Problem Statement

Definition

Constraints

Examples