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?
// 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 :-)