# 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

| Item | Meaning |
|---|---|
| Input | Digit `d`, range `[low, high]` |
| Output | Total occurrences of `d` in all numbers in the range |

Function shape:

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

## Examples

Example 1:

```python
d = 1, low = 1, high = 13
```

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

Answer:

```python
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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `d=1, [1,13]` | `6` | Count all 1s in 1-13 |
| `d=0, [1,92]` | `9` | Count all 0s in 1-92 |