Problem statement

https://leetcode.com/problems/digit-count-in-range/

Solution

This problem can be solved using the technique I called digit build: the idea is to construct digit by digit and check number of cases for each group of numbers. First of all notice, that if we know how to solve this problem in range [1, limit], then we can solve original problem. Let us consider example: limit = 142857. Then all numbers smaller than limit can be separated into the following groups:

?*****, where ? is here is smaller than 1. Also we need to avoid numbers, which start with 0, so in this case this group is empty.

1?****, where ? is here can be [0, 1, 2, 3] and * denote any digit.

14?***, where ? here is range [0, 1] and again * is any digit.

142?**, where ? in range [0, 1, 2, 3, 4, 5, 6, 7]

1428?*, where ? in range [0, 1, 2, 3, 4]

14285?, where ? in range [0, 1, 2, 3, 4, 5, 6]

Let us know discuss the steps of our algorithm:

  1. Transform limit to string, it will be simpler to work with. Also we add 1 to it, because this will work for open interval, whereas we want close interval.
  2. ans will be total number of digits found, k is length of string and q will be to count number of digits s in prefixes of string.
  3. Now we iterate digit by digit and do the following steps:
    1. Transform this digit back to integer.
    2. Update q: number of digits d in prefix: we do it in advance, so when we evaluate part3 we will subtract it, see more details later.
    3. If t == 0, it means that we have current digit equal to 0 or t == 1 and i == 0, we continue, because we have empty group here, like in our example.
    4. part1 is how many times we have digit d instead of * in our groups. If i == 0, then instead of ? we chan have t-1 numbers, in opposite case we can have t numbers. Also, for each of k-i-1 places of * we can put digit d and fill all other places with any of the 10 options. In total, we have 10**(k-i-2)*(k-i-1)*(t-(i==0)) options.
    5. part2 is how many times we have digit d in ? place. If both i == 0 and d == 0, then we can not put ? to 0: we will have number starting with zero in this case. Also d should be <= t-1, so if it is not the case we have 0 options as well. Finally, we have 10**(k-i-1) options, becauswe we can put any numbers to * symbol.
    6. part3 is how many times we have digit d in the resp part of the number. First of all, as I mentioned, we already updated q, and we did it in advance, so we subtract int(t==d) here. (the reason we updated it in advance to deal with continue case in 3.3). Total number of digits we have here is 10**(k-i-1), because we can choose any digits for *, multiplied by t, because we have t options to choose ? and multiplied by updated q: number of times we have digit d in our prefix. Note, that we will handle the case ?***** for say number 231251 here correctly, even though we have t-1 options for ?, but here updated q will be equal to 0.
    7. Update our ans, adding all 3 parts here.
  4. Finally, we need to deal with numbers with 1, 2, ..., k-1 digits as well, for this we can calculate directly number of occurences with direct combinatorial formula.

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 digitsCount(self, d, low, high):
        def helper(d, limit):
            l_str = str(limit + 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))

        def full(d, n):
            return 10**(n-1)*(9*n+1)//10 if d != 0 else 10**(n-1)*(9*n-9)//10
        
        return helper(d, high) - helper(d, low - 1)