Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$.

share|cite|improve this question

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

share|cite|improve this answer
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: – 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}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.