Problem statement

https://binarysearch.com/problems/Digital-Lake/

Solution 1

Almost the same as Leetcode 1067 - Digit Count in Range, so we can reuse code.

Complexity

It is O(k), where k is the length of the biggest among low and high. Note also, that here we use exponents of 10, which is in fact not truly O(1), but for small values like we have we can assume that it is O(1). If we imagine, that the problem need to be solved for much bigger numbers and get answer some module M, then this algorithm can be easily adapted to have O(k) complexity.

Code

class Solution:
    def solve(self, n, d):
        def full(d, n):
            return 10**(n-1)*(9*n+1)//10 if d != 0 else 10**(n-1)*(9*n-9)//10

        l_str = str(n + 1)
        ans, k, q = 0, len(l_str), 0
        
        for i in range(k):
            t = int(l_str[i])
            q += (t == d)
            if t == 0 or t == 1 and i == 0 : continue
            part1 = int(10**(k-i-2)*(k-i-1)*(t-(i==0)))
            part2 = int(t-1 >= d) * 10**(k-i-1) if i > 0 or d > 0 else 0
            part3 = (q-(t==d)) * t * 10**(k-i-1)
            ans += part1 + part2 + part3
    
        return ans + sum(full(d, i) for i in range(1, k))

Solution 2

We can also make it easiry with recursion

Let’s take n = 845 as an example. We first calculate the answer for n // 10 = 84. Then if we multiply this answer by 10 and add 84, we get the count for numbers between 1 and 849. Then we manually count between 846 and 849 using str.count() and remove them.

One edge case is when d = 0, when we have to subtract one from the answer since we are counting starting from 1 instead of 0.

Complexity

It is O(k^2), using previous solution notations. However it is possible to extend this algorithm to make it O(k), if we pass i as parameter where we process str(n)[:i].

Code

### not mine code
class Solution:
    def solve(self, n, d):
        if n < 10: return int(d <= n) - (d == 0)

        k = n // 10
        ans = self.solve(k, d) * 10 + k + (d != 0)

        m = n // 10 * 10 + 9
        while m > n:
            ans -= str(m).count(str(d))
            m -= 1
        return ans