Find how many numbers do not contain the digit n in the range from a to b

algorithmspuzzle

How to find how many numbers do not contain the digit $5$ in the range from $[a,b]$, where $a$ and b are integers and $b ≥ a$

Subject to condition, 5 can be various positions of the number.like $345$ includes $5$ and $1576$ includes $5$ in different positions.

Examples:

[1,9] -> {1,2,3,4,6,7,8,9} -> Result 8
[4,17] -> {4,6,7,8,9,10,11,12,13,14,16,17} -> Result 12
[98, 990] -> Result 639

I am still moving from what I know, and this is the search for such numbers in the ranges 1 – 10, 1 – 100, 1 – 1000.

a = 1; b = 1000; с – number of digits in 1000, m – number of digits without 5
$$n = m^c also (9^3 = 729)$$

All calculations are for integer values.

Yes, indeed, this is a task related to programming, but the logic and calculation are mathematical.Source

Best Answer

Problem becomes trivial if you :

  • Insist on zero filling on the left. This is permitted, because the digit whose occurrences are being interrogated is not $0$. So, for example, interpreting $(10)$ as $(0010)$ does not alter whether a number contains at least one occurrence of the digit $5$.

  • Crouch the problem in a symmetric range. For instance, one example of a symmetric range would be the numbers $0000$ thru $9999$. Here, when examining each of the numbers from $0$ through $9999$, inclusive, it is clear that within each of the $4$ digit places, from right to left (i.e. the $10^0$ place, the $10^1$ place, the $10^2$ place, and the $10^3$ place) you see the $0$ through $9$ pattern over and over and over.

  • Convert the problem from a counting (i.e. Combinatorics) problem into a Probability (i.e. frequency) problem.

For example, suppose that you wanted to know how many of the numbers in the range $0000$ through $9999$ do not contain at least one occurrence of the digit $5$.

Because of the symmetry of the range, you can regard the occurrence of the digit $5$ as actually encapsulating $4$ independent events: namely, the occurrence of the digit $5$ in position $~10^k ~: ~k \in \{0,1,2,3\}.$

Here, the probability that a number chosen at random will not have the digit $5$ in position $k$ is $~\displaystyle \frac{9}{10}.$

Therefore, the count of the numbers in the range $0000$ through $9999$ inclusive that do not contain at least one occurrence of the digit $5$ must be

$$10^4 \times \left[\frac{9}{10}\right]^4 = 9^4.$$

Related Question