## Weekend Programming Challenge – Week #67 Solutions

We got 25 solutions!

• Python x10
• C x4
• C++ x4
• Java x2
• Ruby x1
• JavaScript x1
• Nimrod x1
• Php x1
• Perl x1

The solutions are on Github as usual.

1. I’m saddened by the number of brute force entries even more than by the over-engineered code. To clarify my entry:

A number of sheets is missing. Each sheet consists of recto (odd-numbered) and verso (even) sides. That’s the way books work. Sometimes blank pages say “this page intentionally left blank” but even then they will have a page number.

Since odd+even=odd, a single sheet cannot be missing. Since odd+odd=even, a pair of sheets could be missing. Since even+even=even, any number of pairs of sheets could be missing. Since sum(range(141)) – Python for 0 to 140 – is 9870, no more than 70 sheets can be missing (a small bug in my program!)

Since the pages are consecutive, they have a “middle”, in this case “306.5”, with 8 sheets either side, pages 291-306 and 307-322 respectively.

My own code could be better – http://goo.gl/yZVCb6 prints the solution in 32 steps (of 86 total) – and as it happens there is only one solution. Exploring the solution space with nested loops of the first page number and the number of pages doesn’t just sadden me, it scares me.

2. ultimateohm
Oct 08, 2014 @ 14:40:47

Solutions 10, 14 and 20 could be O(sqrt(n)).
I like solution 14. Simple, no floating-point, mul, div, mod operations.
Another solution I miss?

• My solution (10) is sqrt – no coincidence in 70*140 being 10K. Thanks for pointing out solution 14 which with integer arithmetic is certainly going to find the first (and only) solution using the sliding window method. I’ll look at runsums from #20 again tomorrow, or rather the link in it.