Today’s code puzzle challenges us to write a program that, given a start number and an end number, find the count of all numbers in that range, inclusive of the start and end, except those with a 5 in them.

My first thought, because I hadn’t thought about it very carefully, is that we could just eliminate any numbers in the range that are divisible by 5. Wrong! What about 10? It’s divisible by 5, but it doesn’t have a digit 5 in it. What about 528? It has a 5 in it, but isn’t divisible by 5.

There’s probably an elegant pure math way to solve this, but I’m not really a mathematician. The way I settled on is to just brute force it: check each digit of each number in the range for 5.

That’s cycling through a lot of stuff. How about we use recursion!

The first part is easy enough, just click through each number in the range. Each number, we send to another recursive function that checks if that number, divided by 10, has a remainder of 5. In that case, we know the number ends with 5, and we can reject it.

If the remainder isn’t 5, then we go ahead and divide the number by 10 and throw away the remainder, then call the remainder test again on the new number. Is that remainder 5? Throw it away. Otherwise divide by 10 and repeat again, until you’ve gone through all the digits.

Here’s how it looks in PHP. The magic is on line 22.