Project Euler Problem #76

September 4, 2010

Read the details of the problem here


How many different ways can one hundred be written as a sum of at least two positive integers?


Simple to solve using the solution to Problem #31 as a base by just assuming that coins with face values of 1-99 are available (as at least two integers are required). Strictly speaking, of course, it’s not necessary to use the coins array here as all values are present and a simple loop would be adequate – however doing it like this, given I had the previous solution available, shows the similarity between that problem and this one (and appealed to my laziness).

def ( total, coins ) = [ 100, (1..<100) ]

def nways = [1] + [0]*total

coins.each { coin ->
  coin.upto(total) { nways[it] += nways[it - coin] }

def answer = nways[total]

This runs in 54 ms. A Java version, which doesn’t use a coins array, runs in 220 microseconds – that’s 245 times faster.

After gaining access to the Project Euler forum for this problem, I found that there is a way to solve it in a much more time-efficient manner using partitions. This would provide a far more scalable solution for solving this kind of puzzle for far larger number ranges.


Groovy features made the loops terse to write but not fundamentally different to a normal Java solution.


One Response to “Project Euler Problem #76”

  1. […] and quick to solve using the solutions to Problem #31 and Problem #76 as a starter. The values of primes just replace the values of coins from Problem #31. It’s a […]

Leave a Reply

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

You are commenting using your 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: