## Modified Coin Change

### November 19, 2019

We solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to create a target amount of money, given an unlimited number of coins of various denominations, and is normally solved by a dynamic programming algorithm.

Today’s task is a variant on that problem: find the minimum number of coins that can be used to create a target amount of money, given an unlimited number of coins of denomination that are powers of 5.

Your task is to write a program to solve the modified coin change problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 2 Responses to “Modified Coin Change”

1. Daniel said

Here’s a solution in Python.

```def modified_cc(n):
out = 0
while n > 0:
n, r = divmod(n, 5)
out += r
return out

print(modified_cc(42))
print(modified_cc(142))
```

Output:

```6
6
```
2. Daniel said

Here’s a solution in C that’s similar to the Python solution I posted earlier.

```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int modified_cc(int n) {
int out = 0;
while (n > 0) {
out += n % 5;
n /= 5;
}
return out;
}

int main(int argc, char* argv[]) {
assert(argc == 2);
int n = atoi(argv);
printf("%d\n", modified_cc(n));
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 42
6

\$ ./a.out 142
6
```