Problem 115 of Project Euler is a continuation of Problem 114. The problem reads

NOTE: This is a more difficult version of problem 114.

A row measuringnunits in length has red blocks with a minimum length ofmunits placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, F(m,n), represent the number of ways that a row can be filled.

For example, F(3, 29) = 673135 and F(3, 30) = 1089155.

That is, form= 3, it can be seen thatn= 30 is the smallest value for which the fill-count function first exceeds one million.

In the same way, form= 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, son= 57 is the least value for which the fill-count function first exceeds one million.

Form= 50, find the least value ofnfor which the fill-count function first exceeds one million.

With the very efficient solution from Problem 114 I couldn’t help just trying to wrap it in a while loop until I found the solution. Such that we have the code

long solutions = 0; int n = 50; int limit = 1000000; int m = n-1; while (solutions < limit) { m++; cache = new long[m + 1]; solutions = F(m, n); }

This will correctly solve the problem in less than 6ms and give the result

The solutions exceeds 1000000 for m=168

There is one thing we can do to speed it up though. Since n is kept constant we can reuse the cache every iteration when increasing m. In a simple version where we just guess on an upper bound of 200 we could implement this as

long solutions = 0; int n = 50; int limit = 1000000; int m = n - 1; cache = new long[200]; while (solutions < limit) { m++; solutions = F(m, n); }

This cuts the execution time to below 2ms. This is as far as I went with this problem.

## Wrapping up

Reusing the recursive code from Problem 114 gives us a really efficient solution to this problem which is stated as harder. However, logically it was a very simple extension of the problem and the solution was again very efficient.

You can find the source code for the problem here.