Digit Count In Range - Leetcode Solution

The problem "Digit Count In Range" on Leetcode asks us to count the number of digits that appear in a range of numbers, between low and high, inclusive.

We need to implement a function that takes three integers as input - low, high, and digit. This function will count the number of occurrences of the digit in all the numbers between low and high, inclusive.

For example, if low=100, high=500, and digit=4, the function should count the number of occurrences of the digit 4 in the numbers between 100 and 500, inclusive, and return the count.

To solve this problem, we need to iterate over each number in the given range and count the number of occurrences of the digit in each number.

One approach to solving this problem is to convert each number in the range to a string and count the number of occurrences of the digit in the string. We can use the string.count() method to count the number of occurrences of the digit in each string.

Here's the Python code for this approach:

def count_digit_range(low, high, digit):
    count = 0
    for i in range(low, high+1):
        count += str(i).count(str(digit))
    return count

Another approach is to extract each digit from each number in the range and compare it with the given digit. We can extract each digit from a number using the modulus operator (%) and integer division (//).

Here's the Python code for this approach:

def count_digit_range(low, high, digit):
    count = 0
    for i in range(low, high+1):
        n = i
        while n > 0:
            if n % 10 == digit:
                count += 1
            n //= 10
    return count

Both approaches have a time complexity of O((high-low)*log10(high)), since we need to iterate over each number in the range and extract each digit, which takes O(log10(high)) time. The space complexity is O(1), since we only need a constant amount of space for the count variable.

1