Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once.

Question

Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once.

Can we have a generalized method to solve this problem?

Answer 1

Let me try another, more detailed answer:

We will call the amount of numbers $\leq N$ that contain all digits $A(N)$. And we say that $N$ has $d(N)$ digits. The smallest number of this kind is $1023456789$, since $0$ can not be the leading digit.

Therefore $A(N) = 0$ if $N < 1023456789$ ($d(N) < 10$).

First, we will find $A(N)$ depending on the number of digits of $N$:

There are $d$ digits. The special digit $0$ may be placed at $d-1$ positions. The $1$ at $d-1$ positions, the $2$ at $d-2$ positions and so on to $9$. Now we have $d-10$ positions left without digit. Let us approximate that any digit may be placed on the free positions. This is just an approximation, since the $0$ must not stand at the leading position and some double counting may be included. However, the error is rather small, especially for big $N$. Everybody may feel free to post a solution to this error in the comments. We combine all this and get

$$ A(d) \approx (d-1)(d-1)(d-2)...(d-9) \cdot 10^{d-10} = (d-1)\dfrac{(d-1)!}{(d-10)!} \cdot 10^{d-10}. $$

With this information we can now compose $A(N)$.

$d(N)$ given by $$ d(N) = \lfloor \log_{10}N \rfloor + 1. $$

Therefore we have as good approximation

$$ A(N) \approx \log_{10}N\dfrac{(\log_{10}N)!}{(\log_{10}N-10)!} \cdot 10^{\log_{10}N-10} $$

and since $\log_{10}N-10 = \log_{10}{\frac{N}{10^{10}}}$:

$$ A(N) \approx \log_{10}N\dfrac{(\log_{10}N)!}{(\log_{10}N-10)!} \cdot \frac{N}{10^{10}}. $$

Answer 2

The first easy use case, is if $N$ is less than 10 digits. In this case, the answer is obviously 0.

Next, take a look at $N$ with 10 digits. The first guess is that there are $10!$ possibilities, however, this would be wrong, as 0 cannot be a leading number. Therefore it would be $9*9!$.

My guess is that you could extrapolate a recursive algorithm using $N_10 = $9*9!$.

Answer 3

Hint: For a number with $d \geq 10$ digits, there are $$ 10! \cdot \prod_{n=0}^{d-11}(d+1-n) $$ combinations of numbers that include all digits. But this does include some double counting.

Also note: The number of digits of your number is $$ \lfloor\log_{10}N \rfloor + 1. $$