Self-divisible Numbers

Problem C - Self-divisible Numbers

Personally, I'd rate this as the 2nd best problem of the set [and not just because I know who wrote it =p] - why? Well, firstly, it's original, approacable, easy to understand, and not heavy on textbook algorithms. Secondly, because it seems so easy.....

You're given two numbers (call them lower and upper), and instructions on how to tell if a number has a certain property ('self-divisible'), and have to output the number of self-divisible numbers between lower and upper [inclusive]. The property is easy to test, so all you do is read in lower, upper, do a for-loop between them, count the self-divisible numbers and you're done - ...
Except this is the first question where bounds are important. Each of the numbers 'consists of K digits, 0 <> - so your numbers are as big as 10⁴⁰⁰. This means:

• You cannot read them as ints. No, you can't even read them in as long long (or long in Java). Yes, you can use a BigInteger in Java if you really want, but parseInt is not going to work.
• You cannot loop from lower to upper. If lower is 3399... and upper is 3500..., then even though there are no self-divisible numbers in that range, you're going to have to count over all the 34... numbers, of which there could be 10³⁹⁸. Waaay too many.

So, if you can't loop from lower to upper, what can you do? The hint again is in the bounds - the number of self-divisible numbers in the range is at most 1 million. All that's left is to go from an O(#numbers in range) algorithm, to one that's roughly O(#self-divisible numbers in the rage).

Here's where the example above comes in handy - any number that starts with 34... can't be self-divisible. Say you're looping from lower to upper, and currently looking at the number X. If it is self-divisible, you add one and look at X+1. If it's not, rather than going to X+2, you find the first digit which makes it not self-divisible, and increment THIS by one. You've then skipped a lot of bad numbers - in fact, it's possible now to show this new algorithm mostly only looks at self-divisible numbers, and is as fast as we want.

The next step is implementing it - I found the best way was to do a simple DFS, where you look at a single digit, using only values that make the current prefix self-divisible [this can be achieved by keeping running totals of the prefix mod 1, mod 2, etc....]. Once you reach the last digit, you have a self-divisible number, and you increment your counter by one. One fiddly bit that remains is to only count numbers within the range lower-upper - but for this, there's a nice trick in storing in your DFS whether your prefix is bounded from below by your lower bound, or from above by your upper bound, and using this to limit the range digits you look at.

(Unjudged) code implementing this idea can be found here.