You are given a positive integer

`$N`

.Write a script to print count of numbers from 1 to

`$N`

that don’t contain digit`1`

.

```
Input: $N = 15
Output: 8
```

There are 8 numbers between `1`

and `15`

that don't contain digit `1`

.
`2, 3, 4, 5, 6, 7, 8, 9`

.

```
Input: $N = 25
Output: 13
```

There are 13 numbers between `1`

and `25`

that don't contain digit `1`

.
`2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25`

.

Let's first focus on generating numbers without a 9. It is not hard to see that \(N^{\text{th}}\) non-negative integer without a 9 can be found by converting \(N\) into base-9. This gives the following sequence:

\(N\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

\(N_9\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 30 | 31 | 32 | 33 | ... |

9-free | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 30 | 31 | 32 | 33 | ... |

If we want to generate the \(N^{\text{th}}\) non-negative integer missing a digit other than 9, as a first step, we still start with convert \(N\) into base-9. Then, of the converted number, we replace the digits 0-8 with the nine digits which are allowed. So, in the case we want numbers without a 1, we convert \(N\) into base-9, then replace 1 by 2, 2 by 3, 3 by 4, etc, till we replace 8 by 9. Any 0 remains as is.

This gives the following table:

\(N\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

\(N_9\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 30 | 31 | 32 | 33 | ... |

1-free | 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 20 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 42 | 43 | 44 | ... |

This is sequence A052383 in the OEIS.

Note that if \(P\) is the \(N^{\text{th}}\) 1-free number, then there are \(N\) 1-free numbers between 1 and \(P\).

We don't want to calculate the \(N^{\text{th}}\) 1-free number, instead we want the reverse. The procedure described above can be simply reversed: starting from the 1-free number, we replace each of the digits 2-9 with the digits 1-8, and we interpret the resulting number as a base-9 number.

But there is one more step we need to do. While we can find the answer for a 1-free number, the input may contain a 1. Consider a number \(N\), and let \(M\) be the largest integer \(\leq N\) such that \(M\) contains no 1. Now there are as many numbers between 1 and \(N\) which do not contain a 1, as there are numbers between 1 and \(M\) which do not contain a 1. This is easy to see: if the amount of numbers which do not contain a 1 differs, there must be a number \(p\), \(M < p \leq N\) which contains a 1. But that contradicts the definition of \(M\). Note that if \(N\) does not contain a 1, then \(M = N\).

Given a number \(N\), it's easy to calculate \(M\), where \(M\) is the largest number less or equal to \(N\) which does not contain a 1: find the leftmost 1 in \(N\), replace this by a 0, and change any following digit by a 9. If \(N\) does not contain a 1, the number is left unmodified.

So, we need to do three things:

- Find the largest number smaller than the input number which does not contain a 1.
- Subtract 1 from each non-zero digit.
- Convert the resulting number from base 9 to base 10.

All three things can be done in a single left to right pass.

The described algorithm is performed in a single left to right pass of the input number. Since the third step involves multiplication of an increasingly larger number, each pass is going to be linear in the number of digits of the input; and we need a number of passes which is linear in the number if digits as well. Which means that if our input number consists of \(d\) digits, the running time of our algorithm is bounded by \(\mathcal{O} (d^2)\). (\(\mathcal{O}(d)\) if you consider multiplication to be a constant time operation).

A tempting way of solving this problem would be to inspect all the numbers from 1 till \(N\), discarding the ones containing a 1, and tallying the remainders. But if we look at the running time of this algorithm, we'll see this is \(\Omega (d \cdot 10^{d-1})\), where \(d\) is the the number of digits of the input number.

How dramatic the difference between both implementations is is shown in the table below. First column is the input number \(N\). Second column is the time (in microseconds) of the solution described above (Perl implementation shown below), while the third column is the running time of:

```
$n = <>;
my $result = grep {!/1/} 1 .. $n;
```

All times are in microseconds:

\(N\) | Time (μsec) | |
---|---|---|

10 | 0.518 | 4 |

20 | 0.846 | 8 |

50 | 0.751 | 19 |

100 | 1.103 | 38 |

200 | 1.158 | 82 |

500 | 0.963 | 184 |

1000 | 1.242 | 364 |

2000 | 1.347 | 759 |

5000 | 1.239 | 1896 |

10000 | 1.400 | 3732 |

20000 | 1.446 | 7650 |

50000 | 1.542 | 17511 |

100000 | 1.389 | 38033 |

200000 | 1.804 | 75876 |

500000 | 1.781 | 168706 |

1000000 | 1.596 | 412139 |

2000000 | 1.885 | 510239 |

5000000 | 1.921 | 1531234 |

10000000 | 1.789 | 3452088 |

20000000 | 2.089 | 8721964 |

50000000 | 2.115 | 470332870 |

In our implementation, an input of a 1,000 digits spits out the answer in less than 0.02 seconds. The naïve way would not finish before the universe ends.

As described above in the section Discussion, we find the answer using a couple of left to right passes of the input number. We can even condense this in a single left to right pass.

We'll keep two variables to keep state, `$result`

, which at the end
contains our answer, and `$seen_one`

, to determine whether we have
spotted a `1`

in our input number. They are both initialized to 0:

```
my $result = 0;
my $seen_one = 0;
```

Then for each digit of our input number (`$n`

) we first multiply
`$result`

by `9`

(since we're converting from base-9 to base-10):

```
foreach my $digit (split // => $n) {
$result *= 9;
```

Then we have a three (or four, but in the fourth case, we don't do anything) cases:

- If we have seen a
`1`

in the input (`$seen_one`

), we add`8`

to`$result`

. The`8`

is a combination of finding the largest 1-free number not exceeding the input, and the shifting of digits by 1. - Else, if
`$digit`

is`1`

, we set`$seen_one`

to true. We don't have to add anything to`$result`

in this case, as this is the first`1`

in the input number, and this would be a`0`

when getting the largest 1-free number smaller than the input number, and a`0`

doesn't contribute when converting bases. - Else, if
`$digit`

isn't`0`

, we add`$digit - 1`

to`$result`

.

In the fourth cases, `$digit`

equals `0`

. In that case, nothing needs
to be done.

```
if ($seen_one) {$result += 8}
elsif ($digit == 1) {$seen_one = 1}
elsif ($digit) {$result += $digit - 1}
```

Now all that is left to be done is print the result:

```
say $result;
```

Find the full program on GitHub.

We also have very similar solutions in AWK, Bash, C, Lua, Node.js, Python, and Ruby.