Problem Statement
In this problem we use the Euro currency. One euro equals 100 cents. All amounts in this problem will be in cents to avoid dealing with non-integer numbers.
Euro coins have the following denominations: 1, 2, 5, 10, 20, 50, 100, and 200 cents. Euro banknotes have the following denominations: 500, 1000, 2000, 5000, 10000, 20000, and 50000 cents.
There are rumors that the European Committee will soon introduce a new banknote worth newBanknote cents.
In this new monetary system, what will be the smallest number of coins and banknotes needed to pay exactly X cents?
You are given the int[] amountsToPay. For each X in amountsToPay answer the above question. Return a int[] containing the answers.
Definition
- Class:
- NewBanknote
- Method:
- fewestPieces
- Parameters:
- int, int[]
- Returns:
- int[]
- Method signature:
- int[] fewestPieces(int newBanknote, int[] amountsToPay)
- (be sure your method is public)
Constraints
- newBanknote will be between 1 and 2*10^9, inclusive.
- amountsToPay will have between 1 and 50 elements, inclusive.
- Each element of amountsToPay will be between 1 and 2*10^9, inclusive.
Examples
4700
{53, 9400, 9401, 30000}Returns: {3, 2, 3, 2 }The new banknote is worth exactly 47 euro. When paying 53 cents, the new banknote is useless. The optimal way uses three coins: 50 + 2 + 1. When paying 94 euro, the optimal solution is to use two new banknotes. When paying 94 euro and 1 cent, the optimal solution is to use two new banknotes and a 1-cent coin. When paying 300 euro, the optimal solution is to use one 100-euro and one 200-euro banknote.1234
{1233, 1234, 1235}Returns: {6, 1, 2 }1000
{1233, 100047}Returns: {6, 6 }The new banknote is utterly useless: we already have 10-euro banknotes. Thus, the answer for any amount is the same as when paying using regular Euro denominations only.
Back to all problems