Funcia
Lv.3digit-dpdpmath

Digit Sums Divisible by K

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given positive integers lo, hi and k, return how many integers x with lo ≤ x ≤ hi have a decimal digit sum divisible by k. For example, 4817 has digit sum 4 + 8 + 1 + 7 = 20, so it counts when k = 5.

Examples

lohikresult
12036
1099109
7720

Example 2 — 19, 28, 37, 46, 55, 64, 73, 82, 91 (a two-digit number's digit sum is at most 18).

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(lo: long, hi: long, k: int) → long

Constraints

  • 1≤1 \le lo ≤\le hi ≤1018\le 10^{18}
  • 1≤1 \le k ≤200\le 200
  • The answer fits in a 64-bit integer.

Expected complexity

Time
O(D * K * 10)
Space
O(D * K)

Examples

lohikExpected
12036
1099109
7720

Hint

Hint

Count f(N) = qualifying numbers in [0, N] and answer f(hi) - f(lo - 1). Build N digit by digit from the front, tracking the digit sum modulo k and whether the prefix still equals N's prefix; once a smaller digit is chosen, the rest is free (precompute ways[r][m] for r free digits reaching remainder m). Checking every number in the range exceeds the time limit; O(D⋅K⋅10)O(D \cdot K \cdot 10) with D≤19D \le 19 digits is enough.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance606verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.