Skip to content

Project Euler Problem 76

February 21, 2012

Frankly, I snooped the approach for solving Project Euler Problem 76 at the times of working on solution to Project Euler Problem 31. I wasn’t very happy with my solution and was looking thru Project Euler Problem 31 Forum for alternative approaches. There I spotted one that is perfectly applicable to solving of the current problem, also belonging to Integer Partition type. It is based on dynamic programming approach: if we try partitioning number n with an addendum x, then how many ways exist to partition number n – x with addendums that are less, or equal, than x? This approach allows finding the answer for this question for addendum i based on answer for the same question for smaller addendums. After growing our addendums from 1 to 99 we eventually get to the number of partitionings for n = 100:

let problem076() =
    let n = 100
    let partitions = Array.zeroCreate (n + 1)
    partitions.[0] <- 1
    for addendum in 1..n - 1 do
        for i in addendum..n do
            partitions.[i] <-
                partitions.[i] + partitions.[i - addendum]

    partitions.[n]
Advertisements

From → Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 77 « In F# Major

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: