LeetCode 1067: Digit Count in Range

Problem Restatement

We are given a digit d (0-9) and a range [low, high].

Return the number of times digit d appears in all integers in [low, high].

The official constraints state that 0 <= d <= 9 and 1 <= low <= high <= 2 * 10^8.

Input and Output

Function shape:

def digitsCount(d: int, low: int, high: int) -> int:
    ...

Examples

Example 1:

d = 1, low = 1, high = 13

Numbers: 1, 2, …, 13. Digit 1 appears in: 1, 10, 11 (twice), 12, 13. Total: 6.

Answer:

6

Key Insight

Use the formula: count(d, n) = count of digit d in [1..n].

Then the answer is count(d, high) - count(d, low - 1).

For count(d, n): iterate over each digit position (ones, tens, hundreds, …) and count how many times d appears at that position.

Algorithm

For each position with place value p:

• Let higher = n // (p * 10), current = (n // p) % 10, lower = n % p.
• If current > d: count += (higher + 1) * p.
• If current == d: count += higher * p + lower + 1.
• If current < d: count += higher * p.
• Special case: d == 0 and the leading position.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def digitsCount(self, d: int, low: int, high: int) -> int:
        def count(d, n):
            if n <= 0:
                return 0
            result = 0
            p = 1
            while p <= n:
                higher = n // (p * 10)
                current = (n // p) % 10
                lower = n % p

                if d == 0:
                    result += (higher - 1) * p + (lower + 1 if current > d else 0) + (lower + 1 if current == d else 0)
                else:
                    if current > d:
                        result += (higher + 1) * p
                    elif current == d:
                        result += higher * p + lower + 1
                    else:
                        result += higher * p
                p *= 10
            return result

        return count(d, high) - count(d, low - 1)

Testing

def run_tests():
    s = Solution()

    assert s.digitsCount(1, 1, 13) == 6
    assert s.digitsCount(0, 1, 92) == 9

    print("all tests passed")

run_tests()