I have to admit I fell for the naive solution until I read davidmmooneys comment. The problem is to find the least amount of coins, not to use as many of the largest denomination coin as possible.

Notice how the last test outputs 4. using this approach we find 25 + 5 + 5 + 5 = 40, although this is true, 20 + 20 = 40 is a better solution as it uses 2 coins.

The following is an improved solution based on the fact that you can divide the problem into sub problems that are also valid. for example if 20 + 20 + 1 + 1 = 42 is the best solution for 42 then 20 + 20 = 40 and 1 + 1 = 2 must be the best solution for 40 and 2 respectively. I start with the fact that you need 0 coins to get an amount of 0, then calculate the best amount for each amount between 0 and the input.

I have to admit I fell for the naive solution until I read davidmmooneys comment. The problem is to find the least amount of coins, not to use as many of the largest denomination coin as possible.

My initial solution was as follows:

Notice how the last test outputs 4. using this approach we find 25 + 5 + 5 + 5 = 40, although this is true, 20 + 20 = 40 is a better solution as it uses 2 coins.

The following is an improved solution based on the fact that you can divide the problem into sub problems that are also valid. for example if 20 + 20 + 1 + 1 = 42 is the best solution for 42 then 20 + 20 = 40 and 1 + 1 = 2 must be the best solution for 40 and 2 respectively. I start with the fact that you need 0 coins to get an amount of 0, then calculate the best amount for each amount between 0 and the input.