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.

```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."""
    
    # Helper function to compute the digit sum of a positive integer
    def digit_sum(n: int) -> int:
        s = 0
        while n:
            s += n % 10
            n //= 10
        return s

    # Helper function to count Harshad numbers from 1 to n
    def count_up_to(n: int) -> int:
        if n < 1:
            return 0
        count = 0
        # Iterate through all possible digit sums s from 1 to 9 * number_of_digits
        # The maximum digit sum for a number <= 10^18 is 9 * 18 = 162
        for s in range(1, 163):
            # The smallest number with digit sum s is s (e.g., s = 1 -> 1, s = 10 -> 19)
            # The largest number with digit sum s is s * 10^k where k is the number of digits
            # We need to find the largest multiple of s that has digit sum s.
            # This is equivalent to finding the largest number <= n that is a multiple of s
            # and has digit sum s.
            
            # The largest number with digit sum s is s * 10^k where k is the number of digits.
            # For a given s, the maximum number is s * 10^k. We want the largest such number <= n.
            # We can iterate over possible lengths k.
            
            max_len = len(str(n))
            max_num = 0
            
            # Try all possible lengths from 1 to max_len
            for k in range(1, max_len + 1):
                # The maximum number with digit sum s and length k is s * 10^(k-1)
                # (e.g., s=10, k=2 -> 10 * 10^1 = 100)
                candidate = s * (10 ** (k - 1))
                if candidate > n:
                    continue
                if digit_sum(candidate) == s:
                    max_num = candidate
            
            if max_num > 0:
                count += max_num // s
        
        return count

    # Adjust L to 1 since 0 is never a Harshad number
    L = max(1, L)
    
    return count_up_to(R) - count_up_to(L - 1)
```

[
  {
    "total": 17,
    "answer": "```python\ndef count_harshad(L: int, R: int) -> int:\n    \"\"\"Return the number of integers x with L <= x <= R that are divisible by\n    the sum of their own decimal digits.\"\"\"\n    \n    # Helper function to compute the digit sum of a positive integer\n    def digit_sum(n: int) -> int:\n        s = 0\n        while n:\n            s += n % 10\n            n //= 10\n        return s\n\n    # Helper function to count Harshad numbers from 1 to n\n    def count_up_to(n: int) -> int:\n        if n < 1:\n            return 0\n        count = 0\n        # Iterate through all possible digit sums s from 1 to 9 * number_of_digits\n        # The maximum digit sum for a number <= 10^18 is 9 * 18 = 162\n        for s in range(1, 163):\n            # The smallest number with digit sum s is s (e.g., s = 1 -> 1, s = 10 -> 19)\n            # The largest number with digit sum s is s * 10^k where k is the number of digits\n            # We need to find the largest multiple of s that has digit sum s.\n            # This is equivalent to finding the largest number <= n that is a multiple of s\n            # and has digit sum s.\n            \n            # The largest number with digit sum s is s * 10^k where k is the number of digits.\n            # For a given s, the maximum number is s * 10^k. We want the largest such number <= n.\n            # We can iterate over possible lengths k.\n            \n            max_len = len(str(n))\n            max_num = 0\n            \n            # Try all possible lengths from 1 to max_len\n            for k in range(1, max_len + 1):\n                # The maximum number with digit sum s and length k is s * 10^(k-1)\n                # (e.g., s=10, k=2 -> 10 * 10^1 = 100)\n                candidate = s * (10 ** (k - 1))\n                if candidate > n:\n                    continue\n                if digit_sum(candidate) == s:\n                    max_num = candidate\n            \n            if max_num > 0:\n                count += max_num // s\n        \n        return count\n\n    # Adjust L to 1 since 0 is never a Harshad number\n    L = max(1, L)\n    \n    return count_up_to(R) - count_up_to(L - 1)\n```",
    "passed": 8,
    "test_error": "    assert 18 == 10\nE            +  where 18 = count_harshad(1, 10)\nE            +  and   10 = _brute(1, 10)\n\ntest_harshad.py:88: AssertionError\n___________________________ test_random_ranges_small ___________________________\n\n    def test_random_ranges_small():\n        rng = random.Random(20260701)\n        for _ in range(60):\n            a = rng.randint(0, 5000)\n            b = rng.randint(0, 5000)\n            lo, hi = min(a, b), max(a, b)\n>           assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)\nE           AssertionError: (69, 2134)\nE           assert 2637 == 406\nE            +  where 2637 = count_harshad(69, 2134)\nE            +  and   406 = _brute(69, 2134)\n\ntest_harshad.py:100: AssertionError\n__________________________ test_random_ranges_larger ___________________________\n\n    def test_random_ranges_larger():\n        rng = random.Random(777)\n        for _ in range(8):\n            a = rng.randint(0, 200_000)\n            b = rng.randint(0, 200_000)\n            lo, hi = min(a, b), max(a, b)\n>           assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)\nE           AssertionError: (60118, 116875)\nE           assert 117000 == 6406\nE            +  where 117000 = count_harshad(60118, 116875)\nE            +  and   6406 = _brute(60118, 116875)\n\ntest_harshad.py:109: AssertionError\n________________________ test_prefix_up_to_one_million _________________________\n\n    def test_prefix_up_to_one_million():\n        # A genuinely larger exact check the oracle can still handle.\n>       assert count_harshad(1, 1_000_000) == _brute(1, 1_000_000)\nE       assert 1800000 == 95428\nE        +  where 1800000 = count_harshad(1, 1000000)\nE        +  and   95428 = _brute(1, 1000000)\n\ntest_harshad.py:114: AssertionError\n=========================== short test summary info ============================\nFAILED test_harshad.py::test_ten_is_harshad - assert 9 == 1\nFAILED test_harshad.py::test_known_small_range - assert 27 == 13\nFAILED test_harshad.py::test_specific_membership - AssertionError: 12\nFAILED test_harshad.py::test_L_equals_R_harshad - assert 0 == 1\nFAILED test_harshad.py::test_inclusive_both_endpoints - assert 9 == 2\nFAILED test_harshad.py::test_full_prefix_equals_oracle_small - AssertionError...\nFAILED test_harshad.py::test_random_ranges_small - AssertionError: (69, 2134)\nFAILED test_harshad.py::test_random_ranges_larger - AssertionError: (60118, 1...\nFAILED test_harshad.py::test_prefix_up_to_one_million - assert 1800000 == 95428\n9 failed, 8 passed in 0.20s"
  },
  {
    "total": 17,
    "answer": "```python\ndef count_harshad(L: int, R: int) -> int:\n    \"\"\"Return the number of integers x with L <= x <= R that are divisible by\n    the sum of their own decimal digits.\"\"\"\n    \n    # Helper function to compute the digit sum of a positive integer\n    def digit_sum(n: int) -> int:\n        s = 0\n        while n:\n            s += n % 10\n            n //= 10\n        return s\n\n    # Helper function to count Harshad numbers from 1 to n\n    def count_up_to(n: int) -> int:\n        if n < 1:\n            return 0\n        count = 0\n        # Iterate through all possible digit sums s from 1 to 9 * number_of_digits\n        # The maximum digit sum for a number <= 10^18 is 9 * 18 = 162\n        for s in range(1, 163):\n            # The smallest number with digit sum s is s (e.g., s = 1 -> 1, s = 10 -> 19)\n            # The largest number with digit sum s is s * 10^k where k is the number of digits\n            # We need to find the largest multiple of s that has digit sum s.\n            # This is equivalent to finding the largest number <= n that is a multiple of s\n            # and has digit sum s.\n            \n            # The largest number with digit sum s is s * 10^k where k is the number of digits.\n            # For a given s, the maximum number is s * 10^k. We want the largest such number <= n.\n            # We can iterate over possible lengths k.\n            \n            max_len = len(str(n))\n            max_num = 0\n            \n            # Try all possible lengths from 1 to max_len\n            for k in range(1, max_len + 1):\n                # The maximum number with digit sum s and length k is s * 10^(k-1)\n                # (e.g., s=10, k=2 -> 10 * 10^1 = 100)\n                candidate = s * (10 ** (k - 1))\n                if candidate > n:\n                    continue\n                if digit_sum(candidate) == s:\n                    max_num = candidate\n            \n            if max_num > 0:\n                count += max_num // s\n        \n        return count\n\n    # Adjust L to 1 since 0 is never a Harshad number\n    L = max(1, L)\n    \n    return count_up_to(R) - count_up_to(L - 1)\n```",
    "passed": 8,
    "test_error": "    assert 18 == 10\nE            +  where 18 = count_harshad(1, 10)\nE            +  and   10 = _brute(1, 10)\n\ntest_harshad.py:88: AssertionError\n___________________________ test_random_ranges_small ___________________________\n\n    def test_random_ranges_small():\n        rng = random.Random(20260701)\n        for _ in range(60):\n            a = rng.randint(0, 5000)\n            b = rng.randint(0, 5000)\n            lo, hi = min(a, b), max(a, b)\n>           assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)\nE           AssertionError: (69, 2134)\nE           assert 2637 == 406\nE            +  where 2637 = count_harshad(69, 2134)\nE            +  and   406 = _brute(69, 2134)\n\ntest_harshad.py:100: AssertionError\n__________________________ test_random_ranges_larger ___________________________\n\n    def test_random_ranges_larger():\n        rng = random.Random(777)\n        for _ in range(8):\n            a = rng.randint(0, 200_000)\n            b = rng.randint(0, 200_000)\n            lo, hi = min(a, b), max(a, b)\n>           assert count_harshad(lo, hi) == _brute(lo, hi), (lo, hi)\nE           AssertionError: (60118, 116875)\nE           assert 117000 == 6406\nE            +  where 117000 = count_harshad(60118, 116875)\nE            +  and   6406 = _brute(60118, 116875)\n\ntest_harshad.py:109: AssertionError\n________________________ test_prefix_up_to_one_million _________________________\n\n    def test_prefix_up_to_one_million():\n        # A genuinely larger exact check the oracle can still handle.\n>       assert count_harshad(1, 1_000_000) == _brute(1, 1_000_000)\nE       assert 1800000 == 95428\nE        +  where 1800000 = count_harshad(1, 1000000)\nE        +  and   95428 = _brute(1, 1000000)\n\ntest_harshad.py:114: AssertionError\n=========================== short test summary info ============================\nFAILED test_harshad.py::test_ten_is_harshad - assert 9 == 1\nFAILED test_harshad.py::test_known_small_range - assert 27 == 13\nFAILED test_harshad.py::test_specific_membership - AssertionError: 12\nFAILED test_harshad.py::test_L_equals_R_harshad - assert 0 == 1\nFAILED test_harshad.py::test_inclusive_both_endpoints - assert 9 == 2\nFAILED test_harshad.py::test_full_prefix_equals_oracle_small - AssertionError...\nFAILED test_harshad.py::test_random_ranges_small - AssertionError: (69, 2134)\nFAILED test_harshad.py::test_random_ranges_larger - AssertionError: (60118, 1...\nFAILED test_harshad.py::test_prefix_up_to_one_million - assert 1800000 == 95428\n9 failed, 8 passed in 0.20s"
  },
  {
    "total": 17,
    "answer": "```python\ndef count_harshad(L: int, R: int) -> int:\n    \"\"\"Return the number of integers x with L <= x <= R that are divisible by\n    the sum of their own decimal digits.\"\"\"\n    \n    # Helper function to compute the digit sum of a positive integer\n    def digit_sum(n: int) -> int:\n        s = 0\n        while n:\n            s += n % 10\n            n //= 10\n        return s\n\n    # Helper function to count Harshad numbers from 1 to n\n    def count_up_to(n: int) -> int:\n        if n < 1:\n            return 0\n        count = 0\n        # Iterate through all possible digit sums s from 1 to 9 * number_of_digits\n        # The maximum digit sum for a number <= 10^18 is 9 * 18 = 162\n        for s in range(1, 163):\n            # The smallest number with digit sum s is s (e.g., s = 1 -> 1, s = 10 -> 19)\n            # The largest number with digit sum s is s * 10^k where k is the number of digits\n            # We need to find the largest multiple of s that has digit sum s.\n            # This is equivalent to finding the largest number <= n that is a multiple of s\n            # and has digit sum s.\n            \n            # The largest number with digit sum s is s * 10^k where k is the number of digits.\n            # For a given s, the maximum number is s * 10^k. We want the largest such number <= n.\n            # We can iterate over possible lengths k.\n            \n            max_len = len(str(n))\n            max_num = 0\n            \n            # Try all possible lengths from 1 to max_len\n            for k in range(1, max_len + 1):\n                # The maximum number with digit sum s and length k is s * 10^(k-1)\n                # (e.g., s=10, k=2 -> 10 * 10^1 = 100)\n                candidate = s * (10 ** (k - 1))\n                if candidate > n:\n                    continue\n                if digit_sum(candidate) == s:\n                    max_num = candidate\n            \n            if max_num > 0:\n                count += max_num // s\n        \n        return count\n\n    # Adjust L to 1 since 0 is never a Harshad number\n    L = max(1, L)\n    \n    return count_up_to(R) - count_up_to(L - 1)\n```",
    "passed": 8,
    "test_error": ""
  }
]