Digit Count in Range

Naive Solution

The most straightforward approach is to iterate through all numbers in the given range [low, high] and, for each number, count the occurrences of the specified digit d. This involves converting each number to a string and then iterating through the string to check each digit.

Code (Python)

def digitsInNumber(num, digit):
    count = 0
    s = str(num)
    for char in s:
        if char == str(digit):
            count += 1
    return count

def digitsCountNaive(d, low, high):
    count = 0
    for i in range(low, high + 1):
        count += digitsInNumber(i, d)
    return count

Complexity Analysis

• Time Complexity: O((high - low + 1) * log(high)), where high - low + 1 is the number of integers in the range, and log(high) is the average number of digits in each number. Converting each number to a string takes O(log(high)) time.
• Space Complexity: O(1), as we use constant extra space.

Optimal Solution: Digit-by-Digit Analysis

A more efficient approach involves analyzing the digits of the numbers in the range directly. We can iterate through each digit position and calculate how many times the digit d appears at that position within the range [1, n]. By calculating the count for [1, high] and subtracting the count for [1, low - 1], we obtain the count for the desired range [low, high]. This prevents us from iterating through all the numbers in the range. Also, we must take into account leading zeroes.

Algorithm

1. Define a function countDigit(n, d) that calculates the number of times digit d appears in the numbers from 1 to n.
2. Convert the number n to a string so we can iterate through the digits from left to right.
3. Iterate through each digit position in the number n.
4. For each position i, calculate:
   • prefix: The number formed by the digits to the left of position i.
   • currentDigit: The digit at position i.
   • suffix: The number formed by the digits to the right of position i.
5. Based on the value of currentDigit compared to d, update the count:
   • If currentDigit < d: The digit d appears prefix * 10^(number of digits in suffix) times.
   • If currentDigit == d: The digit d appears prefix * 10^(number of digits in suffix) + suffix + 1 times.
   • If currentDigit > d: The digit d appears (prefix + 1) * 10^(number of digits in suffix) times.
6. Handle the special case when d == 0 to avoid counting leading zeros.
7. The result would be countDigit(high, d) - countDigit(low - 1, d).

Code (Python)

def countDigit(n, d):
    s = str(n)
    length = len(s)
    count = 0
    for i in range(length):
        prefix = 0 if i == 0 else int(s[:i])
        currentDigit = int(s[i])
        suffix = 0 if i == length - 1 else int(s[i+1:])
        powerOf10 = 10 ** (length - i - 1)

        if d == 0:
            if i == 0:
                continue # leading zeroes
            if currentDigit > d:
                count += prefix * powerOf10
            elif currentDigit == d:
                count += prefix * powerOf10 + suffix + 1
            else:
                count += (prefix - 1) * powerOf10
        else:
            if currentDigit > d:
                count += (prefix + 1) * powerOf10
            elif currentDigit == d:
                count += prefix * powerOf10 + suffix + 1
            else:
                count += prefix * powerOf10
    return count

def digitsCount(d, low, high):
    return countDigit(high, d) - countDigit(low - 1, d)

Complexity Analysis

• Time Complexity: O(log(high) + log(low)), as we iterate through the digits of high and low separately. Thus, the complexity is proportional to the number of digits in the input numbers.
• Space Complexity: O(1), as we use constant extra space.

Edge Cases

• d = 0: Special handling is required for the case where d is 0 to avoid counting leading zeros.
• low = 0: The algorithm should correctly handle the case where the lower bound of the range is 0. In our optimal implementation, low - 1 is passed, which becomes -1 which the code handles correctly.
• low = high: When the range contains a single number, the algorithm should return the correct count.
• Large ranges: The algorithm is optimized for large ranges, as it does not iterate through all numbers in the range.