algo-dp-01

# Counting Harshad numbers in a range

Implement a file **`solution.py`** containing a function `count_harshad` that
counts how many integers in a closed range are **Harshad numbers**.

```python
def count_harshad(L: int, R: int) -> int:
    """Return the number of integers x with L <= x <= R that are divisible by
    the sum of their own decimal digits."""
```

## Definitions

For a positive integer `x`, let `digitsum(x)` be the sum of its decimal digits
(e.g. `digitsum(132) = 1 + 3 + 2 = 6`).

`x` is a **Harshad number** (also called a *Niven number*) iff `x > 0` and

```
x % digitsum(x) == 0
```

i.e. `x` is divisible by the sum of its own digits. For example:

- `18` is Harshad: `digitsum(18) = 9`, and `18 % 9 == 0`.
- `11` is **not** Harshad: `digitsum(11) = 2`, and `11 % 2 == 1`.
- Every one-digit number `1..9` is Harshad (each divides itself).

The integer `0` is **never** a Harshad number: its digit sum is `0` and division
by zero is undefined, so it must **not** be counted.

## Task

Given `L` and `R` with `0 <= L <= R`, return the count of Harshad numbers `x`
satisfying `L <= x <= R`. **Both endpoints are inclusive.**

## Constraints

- `0 <= L <= R <= 10**18`.

The upper bound is far too large to enumerate the range one integer at a time —
counting `10**18` numbers individually is hopeless. Your solution must be able to
answer queries near the maximum bound **quickly** (well under a second for a
single call in the worst case). This forces a counting approach rather than
brute-force iteration.

## Examples

```python
assert count_harshad(1, 9) == 9        # all single digits
assert count_harshad(10, 10) == 1      # digitsum 1 divides everything
assert count_harshad(11, 11) == 0      # 11 % 2 != 0
assert count_harshad(1, 20) == 13      # 1..9, 10, 12, 18, 20
assert count_harshad(0, 0) == 0        # 0 is never Harshad
assert count_harshad(1, 100) == 33
assert count_harshad(1, 1000) == 213
assert count_harshad(100, 200) == 27
```

## Notes

- The range is inclusive on both ends.
- A range that begins at `0` gives the same answer as one beginning at `1`
  (since `0` is never counted): `count_harshad(0, R) == count_harshad(1, R)`.
- You may assume the inputs are non-negative integers with `L <= R`.

import random
import time

import pytest

from solution import count_harshad


# ---------------------------------------------------------------------------
# Independent, obviously-correct oracle (feasible only for small bounds).
# ---------------------------------------------------------------------------
def _digit_sum(x: int) -> int:
    s = 0
    while x:
        s += x % 10
        x //= 10
    return s


def _is_harshad(x: int) -> bool:
    if x <= 0:
        return False
    ds = _digit_sum(x)
    return x % ds == 0


def _brute(L: int, R: int) -> int:
    return sum(1 for x in range(L, R + 1) if _is_harshad(x))


# ---------------------------------------------------------------------------
# Tiny hand-checked cases.
# ---------------------------------------------------------------------------
def test_single_digits_all_harshad():
    # 1..9 are each divisible by themselves.
    assert count_harshad(1, 9) == 9


def test_ten_is_harshad():
    # digit sum 1, 10 % 1 == 0
    assert count_harshad(10, 10) == 1


def test_eleven_is_not_harshad():
    # digit sum 2, 11 % 2 == 1
    assert count_harshad(11, 11) == 0


def test_known_small_range():
    # Harshad in [1,20]: 1..9, 10, 12, 18, 20  -> 13
    assert count_harshad(1, 20) == 13


def test_specific_membership():
    for x in (12, 18, 20, 21, 24, 27, 100, 102):
        assert count_harshad(x, x) == 1, x
    for x in (11, 13, 14, 19, 23, 101):
        assert count_harshad(x, x) == 0, x


# ---------------------------------------------------------------------------
# Boundary / edge cases.
# ---------------------------------------------------------------------------
def test_zero_never_counted():
    # 0 has digit sum 0 -> not a Harshad number, division undefined.
    assert count_harshad(0, 0) == 0


def test_range_starting_at_zero_matches_starting_at_one():
    assert count_harshad(0, 500) == count_harshad(1, 500)


def test_empty_when_L_equals_R_non_harshad():
    assert count_harshad(13, 13) == 0


def test_L_equals_R_harshad():
    assert count_harshad(24, 24) == 1


def test_inclusive_both_endpoints():
    # 20 and 21 are both Harshad; range should include both ends.
    assert count_harshad(20, 21) == 2


def test_full_prefix_equals_oracle_small():
    for N in (1, 2, 5, 9, 10, 20, 50, 99, 100, 200, 999, 1000):
        assert count_harshad(1, N) == _brute(1, N), N


# ---------------------------------------------------------------------------
# Randomised cross-checks against the brute-force oracle.
# ---------------------------------------------------------------------------
def test_random_ranges_small():
    rng = random.Random(20260701)
    for _ in range(60):
        a = rng.randint(0, 5000)
        b = rng.randint(0, 5000)
        lo, hi = min(a, b), max(a, b)
        assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)


def test_random_ranges_larger():
    rng = random.Random(777)
    for _ in range(8):
        a = rng.randint(0, 200_000)
        b = rng.randint(0, 200_000)
        lo, hi = min(a, b), max(a, b)
        assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)


def test_prefix_up_to_one_million():
    # A genuinely larger exact check the oracle can still handle.
    assert count_harshad(1, 1_000_000) == _brute(1, 1_000_000)


# ---------------------------------------------------------------------------
# Additivity / consistency (works for bounds far beyond brute force).
# ---------------------------------------------------------------------------
def test_additivity_over_split_points():
    rng = random.Random(42)
    for _ in range(15):
        lo = rng.randint(0, 10_000)
        mid = rng.randint(lo, lo + 20_000)
        hi = rng.randint(mid, mid + 20_000)
        total = count_harshad(lo, hi)
        parts = count_harshad(lo, mid) + count_harshad(mid + 1, hi)
        assert total == parts, (lo, mid, hi)


def test_large_bounds_additive_consistency():
    # Bounds well past what brute force can enumerate; we only assert internal
    # consistency (and that the DP terminates quickly).
    splits = [
        (1, 123_456_789, 999_999_999),
        (10_000_000, 543_210_000, 1_000_000_000),
    ]
    for lo, mid, hi in splits:
        assert count_harshad(lo, hi) == count_harshad(lo, mid) + count_harshad(mid + 1, hi)


def test_large_bound_completes_in_time():
    start = time.time()
    val = count_harshad(1, 1_000_000_000)
    elapsed = time.time() - start
    assert val > 0
    # Must be an efficient digit DP, not enumeration.
    assert elapsed < 20.0, f"too slow: {elapsed:.1f}s"

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

Looking at this problem, I need to count Harshad numbers in a range [L, R] where both L and R can be up to 10^18. Since brute force iteration is impossible for such large ranges, I need a digit dynamic programming (digit DP) approach.

The key insight is that for a number to be a Harshad number, it must be divisible by the sum of its digits. The sum of digits for numbers up to 10^18 is at most 9*18 = 162, so there are only 162 possible digit sums.

I can use digit DP where I count numbers in [0, R] that are Harshad numbers, then use the standard technique: count_harshad(L, R) = count_up_to(R) - count_up_to(L-1).

For the digit DP, I'll need to track:
1. Position in the number (from most significant to least)
2. Whether we're tight to the upper bound
3. The current digit sum
4. The current value modulo some number

But here's the clever part: since we need the final number to be divisible by its digit sum, and the digit sum can only be 1-162, I can run separate DP for each possible digit sum s, counting numbers where:
- The digit sum equals s
- The number is divisible by s

For each possible digit sum s (from 1 to 162), I'll count how many numbers ≤ R have digit sum s and are divisible by s. Then sum over all s.

The DP state will be: (position, tight, current_sum, remainder_mod_s)

Since we're checking divisibility by s, the remainder is modulo s, which is at most 162.

Let me implement this:

```python
def solution():
    pass

def count_harshad(L: int, R: int) -> int:
    """Return the number of integers x with L <= x <= R that are divisible by
    the sum of their own decimal digits."""
    if L == 0:
        return count_up_to(R)
    return count_up_to(R) - count_up_to(L - 1)


def count_up_to(n: int) -> int:
    """Count Harshad numbers in [0, n]"""
    if n < 0:
        return 0
    if n == 0:
        return 0
    
    # Convert number to list of digits
    digits = [int(d) for d in str(n)]
    num_digits = len(digits)
    
    total = 0
    
    # For each possible digit sum s (1 to 9*18=162)
    max_digit_sum = 9 * num_digits
    
    for s in range(1, max_digit_sum + 1):
        # Count numbers <= n with digit sum s that are divisible by s
        count = count_with_digit_sum_and_mod(digits, s)
        total += count
        
    return total


def count_with_digit_sum_and_mod(digits, target_sum):
    """Count numbers <= given digit list that have digit sum == target_sum and are divisible by target_sum"""
    n = len(digits)
    
    # dp[pos][tight][sum][mod] = count
    # But we can optimize by only tracking states that are reachable
    
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(pos, tight, current_sum, remainder):
        # pos: current position (0-indexed from left)
        # tight: whether we're still bounded by the original number
        # current_sum: sum of digits so far
        # remainder: current number mod target_sum
        
        if pos == n:
            # We've formed a complete number
            # Check if digit sum equals target_sum and number is divisible by target_sum
            return 1 if (current_sum == target_sum and remainder == 0) else 0
        
        limit = digits[pos] if tight else 9
        total = 0
        
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_sum = current_sum + d
            # If sum already exceeds target, no point continuing
            if new_sum > target_sum:
                continue
            new_remainder = (remainder * 10 + d) % target_sum
            total += dp(pos + 1, new_tight, new_sum, new_remainder)
        
        return total
    
    result = dp(0, True, 0, 0)
    
    # Clear cache to avoid memory issues for multiple calls
    dp.cache_clear()
    
    return result
```