Number of numbers without a given digit $n$ ($1\leq n \leq 9$)?

Given a number $m$, say $9874,$ how can I find the number of natural numbers before $9874$ without the number $3$ in it? I got this question for an interview. I was able to solve the problem for $2$ digits and $3$ digit numbers but wasn't able to come up with a generalized algorithm to solve this problem, where the input ranges from $1 \leq m < 10^{16}$.

-

Hint: Start by finding the number of such numbers up to $8999$.

-
I guess your answer is specific to the number 9874... But how do I write a generalized algorithm when there are arbitrary digits involved? Thanks. –  Sandeep Jul 24 '13 at 2:17
I was looking for something like this: oeis.org/A061217 –  Sandeep Jul 24 '13 at 2:40
If you understand how to do it for $9874$ (and also for numbers that have a $0$, $1$ or $2$), you can generalize... –  Robert Israel Jul 24 '13 at 3:56

Proposed that the number of representation:$$a_{15}a_{14}\ ...\ a_{1}a_{0}$$ the given number $n$ and the number of numbers include $n$ before $a_ia_{i-1}\ ...\ a_0$ is $S_i$($0 \le i\le 15$).

$$S_0 = \begin{cases} 1, & a_0 \ge n \\ 0, & a_0 \lt n \\ \end{cases}$$

$$S_i = \begin{cases} a_i * S_{i-1} + 10^i, & a_i\ge n \\ (a_i+1) * S_{i-1}, & a_i\lt n \\ \end{cases} \ \ \ \ i>0$$

The result is $a_{15}a_{14}\ ...\ a_{1}a_{0} - S_{15}$

For example find the number of numbers not include 3 before 9874 in your question: Given the represent $$a_{15}=a_{14}=...a_4 = 0,a_3 = 9,a_2 = 8,a_1 = 7,a_0 =4$$ $$n = 3$$ According to the $S_i$ above: $$S_{15} = S_{14} = ... = S_3$$ $$S_3 = 9*S_2+10^3$$ $$S_2 = 8*S_1+10^2$$ $$S_1 = 7*S_0+10$$ $$S_0 = 1$$

So $S_{15} = 2124$, answer is 9874 - $S_{15}$

-