Interviewstreet: Lucky Numbers

Here is the problem description.

This one was great!  Earlier today I was having a fair amount of difficulty with the supposedly simpler Median problem, which shouldn't have been too bad -- for some reason I kept failing three test cases, how frustrating! -- but I am now much happier that I have a solution to Lucky Numbers.  :)

The key was to formulate the problem in terms of dynamic programming.  We don't actually have to range over all of the numbers -- we can knock out lots of numbers all at once by recognizing that, when we have a set of D digits which may all range freely from 0 to 9 (inclusive), we can find the number of lucky numbers by examining sets of D-1 digits (for which we establish an a priori sum of digits and sum of squares of digits based on the value of digit 1 of D).

Of course, this does not quite do the trick, as our inputs A and B are never just 0 and {9}*n for some n -- they are generally more restrictive.  Fortunately, we can use the aforementioned precomputation to efficiently handle this more restrictive case.  ;)