Project Euler — Problem 31 Solution

Problem

In Eng­land the cur­ren­cy is made up of pound, £, and pence, p, and there are eight coins in gen­er­al cir­cu­la­tion:

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

It is pos­si­ble to make £2 in the fol­low­ing way:

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

How many dif­fer­ent ways can £2 be made using any num­ber 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 real­ly, see here for the coin change algo­rithm which I’ve used in my solu­tion.