If you care about the result more than the method, an equivalent function can be written that runs in the same time as a power function (possibly O(log(n))) rather than O(n*log(n)).

To start, we solve the related problem of counting all 1s in all numbers between 0 and 10^

*x*, exclusive (where "^" means exponentiation). Let this number be

*dc*(

*x*) (think "digit count"). Thinking recursively, note

*dc*(1)=1. Assume we can calculate

*dc*(

*x*-1). We can then calculate

*dc*(

*x*) by breaking up the 1s we need to count into leading digits and trailing digits. That is, count the leading 1s in numbers 10^(

*x*-1) through 2*10^(

*x*-1) - 1, inclusive (below, these numbers are written as the patterns "10*" and "19*"), and calculate the trailing 1s in all the numbers between 0 and 10^

*x*, which can be done using

*dc*(

*x*-1). With double angle brackets indicating the sections of numbers to count,

*dc*(

*x*) can be calculated by counting

«1»0* .. «1»9* and

0«0*» .. 9«9*». In the first case, there are 10^(

*x*-1) numbers, hence 10^(

*x*-1) leading ones. In the latter case, there are

*dc*(

*x*-1) trailing digits of interest for any given leading digit, and 10 leading digits, for a total of 10 *

*dc*(

*x*-1) digits of interest.

Code:

```
dc(1) = 1
(«1»0* .. «1»9*) (0«0*» .. 9«9*»)
dc(x) = 10 ^ (x-1) + 10 * dc(x-1)
```

We can do one better, writing dc as the explicit function "

*x* * 10^(

*x*-1)" rather than a recursive function. Note

*dc*(1) = 1 = 1 * 10^0. Now assume

*dc*(

*x*-1) = (

*x*-1) * 10^(

*x*-2). Then

Code:

```
dc(x) = 10 ^ (x-1) + 10 * dc(x-1)
= 10 ^ (x-1) + 10 * ((x-1) * 10^(x-2))
= (1 + x-1) * 10 ^ (x-1)
= x * 10^(x-1) QED
```

Note that though we set out to count 1s, the above works for any digit from 1 through 9. It also works for 0, if we include the leading 0s normally left out of the representation (e.g. "0001").

Now for the original problem: counting a digit

*d* in numbers from 1 through

*k**10^

*x*. Actually, let me amend this to not include

*k**10^

*x*, as it's simpler to solve without and can be covered in a special case. We'll call this number

*pdc*(

*k*,

*x*,

*d*) (think "partial digit count"). Note that these two functions use

*x* differently, as

*dc*(

*x*) doesn't include 10^

*x*, whereas

*pdc*(

*k,x,d*) does include 10^x.

To solve this problem, we can take the same approach of figuring out how to count these digits by breaking down the numbers into patterns. If

*d*<

*k*, there are basically the same two cases: «d»0* .. «d»9* and 0«0*»..(k-1)«9*». However, the number of

*d* this time is 10^

*x*, and each «0*»..«9*» is

*dc*(

*x*), for a total of 10^

*x*+

*k**

*dc*(

*x*). If

*d*≥

*k*, then there are no numbers with leading

*d*s in the range, so there are only the 0«0*»..(k-1)«9*» to count. If you want to include

*k**10^

*x* in the range, the only change you need to make is when

*d*=

*k*, in which case there's an additional

*d* to count, or when

*d*=0, if you want to allow counting 0s (which I won't bother with).

Code:

```
(«d»0* .. «d»9*) (0«0*» .. (k-1)«9*»)
pdc(k,x,d), d<k = 10 ^ x + k * dc(x)
= 10 ^ x + k * x * 10^(x-1)
= (10 + k * x) * 10^(x-1)
(0«0*» .. (k-1)«9*»)
pdc(k,x,d), d>k = k * dc(x)
= k * x * 10^(x-1)
pdc(k,x,d), d=k = 1+k * x * 10^(x-1)
```

Final C function:

Code:

```
long count_digits_from_range(k,x,d) {
if (d < k) {
return (10 + k*x) * pow(10,x-1);
} else if (d==k) {
return 1 + k * x * pow(10,x-1);
} else {
return k * x * pow(10,x-1);
}
}
```

Time: 1.55 µs unoptimized, compared to 24s optimized (-O3) for the original, which is a speedup of over 1.5e7 times faster.

Addendum: 5e8 isn't the only fixed point. From the formula in

*pdc*, we can get fixed points whenever

*d*<

*k* and (10+

*k**

*x*)*10^(

*x*-1) =

*k**10^

*x*, or

*d*>

*k* (

*d*≥

*k*, if we don't include k*10^x) and

*k**10^

*x*=

*k**

*x**10^(

*x*-1), where 0 < k < 10. The former is equivalent to

*x*=10(

*k*-1)/

*k*, which leads to the solutions (k,x) in [(1, 0), (2, 5), (5, 8)] when

*d*<

*k*:

Code:

```
# Python
>>> [(k,int(x)) for k,x in [(k, 10.0*(k-1.0)/k) for k in range(1,10)] if int(x)==x]
[(1, 0), (2, 5), (5, 8)]
```

The latter is much simpler to solve: 10=

*x* when

*d*>

*k*, giving fixed points of 1e10, 2e10, ... 8e10. 9e10 is a fixed point if k*10^x isn't included in the count.