Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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

share|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: 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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.