NewMoneySystem | Topcoder Archive

Problem Statement

You are creating the money system for a new game. The requirements are as follows:

There will be exactly K different banknote values.
The value of the smallest banknote will be equal to one dollar.
The value of the i-th banknote will be equal to the value of the (i-1)-th banknote multiplied by 2, 3, 4 or 5.

The initial capital of a player will be N dollars, so you want to choose banknote values in such a way that minimizes the number of banknotes required to make N dollars. Assume that you have an infinite supply of banknotes for each value.

You will be given two integers N and K. Due to technical reasons, N will be given as a String with no leading zeros. Return the minimal number of banknotes required to make exactly N dollars. Note that you must minimize the number of actual banknotes, not the number of banknote values (see examples).

Definition

Class:: NewMoneySystem
Method:: chooseBanknotes
Parameters:: String, int
Returns:: long
Method signature:: long chooseBanknotes(String N, int K)
(be sure your method is public)

Constraints

N will be an integer between 1 and 1018, inclusive, with no leading zeros.
K will be between 1 and 100, inclusive.

Examples

```
"1025"
```
```
6
```
```
Returns: 2
```
The best set of banknote values is {1, 4, 16, 64, 256, 1024}. 1025 = 1024 + 1.
```
"1005"
```
```
5
```
```
Returns: 3
```
The best set of banknote values is {1, 5, 25, 100, 500}. 1005 = 2 * 500 + 5.
```
"12000"
```
```
14
```
```
Returns: 1
```

"924323565426323626"

Returns: 924323565426323626

The answer can be rather big.

```
"924323565426323626"
```
```
50
```
```
Returns: 10
```

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.