Project Euler – Problem 76 Solution

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!

1 thought on “Project Euler – Problem 76 Solution”

  1. Pingback: Project Euler - Problem 77 Solution | theburningmonk.com

Leave a Comment

Your email address will not be published. Required fields are marked *