Project Euler – Problem 31 Solution

Problem

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

Solution

// the total and available coins
let total, coins = 200, [1;2;5;10;20;50;100;200]

// implement the coin change algorithm
let rec count n m =
    if n = 0 then 1
    else if n < 0 then 0
    else if (m <= 0 && n >= 1) then 0
    else (count n (m-1)) + (count (n-coins.[m-1]) m)

let answer = count total coins.Length

Not much for me to add here really, see here for the coin change algorithm which I’ve used in my solution.

Subscribe to my newsletter and get new contents delivered straight to your inbox :-)