Editorial for Digit Sum

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let $f(N)$ be the number of integers $x$ with $0 \le x \le N$ whose digit sum is divisible by $M$ . The answer is $f(R) - f(L - 1)$ .

To compute $f(N)$ , process the digits of $N$ from left to right. Keep counts for numbers that are already strictly smaller than the prefix of $N$ , grouped by their digit-sum remainder modulo $M$ . Also keep the current remainder of the one prefix that is still exactly equal to $N$ 's prefix.

When reading a new digit with limit $d$ , any already-smaller prefix can append any digit from $0$ to $9$ . The tight prefix can append digits from $0$ to $d - 1$ to become smaller, or append $d$ to remain tight. At the end, all smaller prefixes with remainder $0$ count, and the tight number $N$ itself counts if its remainder is $0$ .

This takes $O(|R| \cdot M \cdot 10)$ time.

Solution (Python)

Code 1

import sys


def subtract_one(s):
    if s == "0":
        return None

    digits = list(s)
    i = len(digits) - 1
    while digits[i] == "0":
        digits[i] = "9"
        i -= 1
    digits[i] = str(int(digits[i]) - 1)

    result = "".join(digits).lstrip("0")
    return result or "0"


def count_up_to(n, m):
    if n is None:
        return 0

    loose = [0] * m
    tight_remainder = 0

    for ch in n:
        limit = ord(ch) - ord("0")
        next_loose = [0] * m

        for remainder, count in enumerate(loose):
            if count == 0:
                continue
            for digit in range(10):
                next_loose[(remainder + digit) % m] += count

        for digit in range(limit):
            next_loose[(tight_remainder + digit) % m] += 1

        loose = next_loose
        tight_remainder = (tight_remainder + limit) % m

    return loose[0] + (1 if tight_remainder == 0 else 0)


def main() -> None:
    tokens = sys.stdin.read().split()
    l, r, m_str = tokens
    m = int(m_str)

    answer = count_up_to(r, m) - count_up_to(subtract_one(l), m)
    print(answer)


if __name__ == "__main__":
    main()

Comments0

No comments yet

Be the first to comment.

Editorial for Digit Sum

Approach

Solution (Python)

Comments0

New comment