## Project Euler Problem #76

### September 4, 2010

Read the details of the problem here

**Summary**

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

**Solution**

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.

**Conclusion**

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

September 4, 2010 at 22:53

[…] 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 […]