Perl Weekly Challenge 126: Count Numbers

by Abigail

Challenge

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.

Example

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.

Discussion

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$$ $$N_9$$ 9-free 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 ... 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 ... 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$$ $$N_9$$ 1-free 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 ... 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 ... 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:

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

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

Efficiency

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).

The naïve way

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. Solution Perl 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.

Other Languages

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