Given a number '$N$' find how many how many numbers are there between $1$ to $N$ that doesn't contain the digit $3$?

Question

You are given a number $N\le 10^{18}$. You need to find out how many numbers there exist in between $1$ to $N$, which doesn't contain the digit $'X'$ in it . Say $N = 5, X=4$

The answer is $4$.

$1, 2, 3, 5$ are the numbers that doesn't contain $4$ in it . How can I solve this problem ?

I repeat between $1$ to $N$. $0$ is not countable. And $X$ will never be $0$.

Answer 1

Original version (mistaken):

Subtract $1$ from every digit in $N$ that is $≥X$. Then interpret $X$ as a base-$9$ number.

Edited to add:

This doesn't work if $N$ contains any digits equal to $X$. For example, if $X=3$, then for $N=20$ or $N=40$ we get $20_9 = 18$ and $30_9 = 27$ numbers respectively; but for $N=30$ we get $26$ numbers, not $20_9=18$ as my procedure predicts.

To get round this, we need a pre-processing stage. So now it looks like this:

1. If $N$ contains any digit equal to $X$, then replace all digits to the right of this $X$ with $9$.
2. Subtract $1$ from every digit in $N$ that is $≥X$.
3. Interpret $N$ as a base-$9$ number.

Answer 2

This looks like a Project Euler problem, or a problem of that kind.
You need to solve this in a combinatorical way. There are many approaches.
E.g. a relatively simple approach is: Count how many $K$-digit ($K \leq 18$) numbers contain the digit $3$. To find this count you have to find how many numbers contain exactly 1,2,...,K digits equal to 3 (that's not so difficult). Then sum over $K$. Say this count/sum is $M$. Then the answer is: $10^{18}-M$.

Answer 3

You can use constructive counting to quickly address the problem. First, we find how many non-leading digits there are in $N.$ Say $N = 9,612.$ The number of non-leading digits for this is $4 - 1 = 3.$

For each non-leading digit of $N,$ we can select any digit but $X.$ Since there are $10$ total digits, and we may pick any digit but $X,$ the number of ways to do this is $9^{n - 1},$ where $n$ is the number of digits in $N.$

The next part is somewhat tricky. We look for the numbers greater than $10^{n}$ and less than $N$ that do not contain $X.$ Hopefully, you can manually count this. Add this to $9^{n - 1}$ from the previous count, and you have your answer.