TopCoder problem "NewCoins" used in Member SRM 458 (Division I Level Two)



Problem Statement

    As a finance minister, Bob decided to make new denominations of coins. If the values of the coins are x1, x2, x3, ... in ascending order then x1 must be 1 and xb must be an integer multiple of xa for all b > a.



He has a list of products sold in his country. The price of the i-th product is price[i]. He wants to minimize the number of coins required to buy each product exactly once. Each product must be purchased separately using coins that total to exactly the value of the product. Using multiple coins of the same denomination is allowed. See example 0 for further clarification.



Return the minimal number of coins required to buy each product exactly once.
 

Definition

    
Class:NewCoins
Method:minCoins
Parameters:int[]
Returns:int
Method signature:int minCoins(int[] price)
(be sure your method is public)
    
 

Constraints

-price will contain between 1 and 50 elements, inclusive.
-Each element in price will be between 1 and 100,000, inclusive.
 

Examples

0)
    
{25, 102}
Returns: 4
Bob can use {1, 25, 100} as the new set of coins. Then, a single coin of value 25 can be used to buy the first product. To buy the second product, one coin of value 100 and two coins of value 1 is sufficient. So, in total, 4 coins can be used to buy all products using the new set of coins.
1)
    
{58}
Returns: 1
One possible set of coins is {1, 58}.
2)
    
{1, 4, 5, 9, 16}
Returns: 7
One possible set of coins is {1, 2, 4, 8, 16}.
3)
    
{1, 1, 1, 1, 1}
Returns: 5
Different products may have the same price.
4)
    
{28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498}
Returns: 62

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10569

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14180&pm=10569

Writer:

rng_58

Testers:

Rustyoldman , timmac , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Dynamic Programming