Presently sponsored by Serverless Guru: Your guide to cloud excellence, helping you every step of your serverless journey, including team training, pattern development, mass service migrations, architecting, and developing new solutions. Speak to a Guru today.
Problem
It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
Solution
// implement the coin change algorithm let rec count n m (coins:int list) = if n = 0 then 1 else if n < 0 then 0 else if (m <= 0 && n >= 1) then 0 else (count n (m-1) coins) + (count (n-coins.[m-1]) m coins) let answer = count 100 99 [1..99]
This is basically problem 31 with a twist, using the same coin change algorithm but substitute the set coins with the numbers less than 100 and you’ll have your solution!
Pingback: Project Euler - Problem 77 Solution | theburningmonk.com