A board game's score sheet lists the points each turn earned: points[i] for turn i. Penalties make some turns negative. A bonus is paid for every stretch of one or more consecutive turns whose total is a multiple of k. Zero and negative multiples count too (0, -3 and 6 are all multiples of 3).
Write subarrays_div_by_k(points: list[int], k: int) -> int: how many such stretches there are. Stretches that overlap, or have the same total, are counted separately.
subarrays_div_by_k([3, -1, 4, 2, -5], 3)
# 7: [3], [3, -1, 4], [3, -1, 4, 2, -5], [-1, 4], [-1, 4, 2, -5], [4, 2], [2, -5]
subarrays_div_by_k([2, 2, 2, 2], 4) # 4: the three [2, 2] and the whole sheet
subarrays_div_by_k([-7], 7) # 1: -7 is a multiple of 7
subarrays_div_by_k([1, 2], 5) # 0
Constraints: 1 <= len(points) <= 2 * 10^5, -10^4 <= points[i] <= 10^4, 2 <= k <= 10^4. The answer can be close to 2 * 10^10, more than 32 bits hold.
⭐ Bonus: totalling every stretch still passes; a speed test with 200,000 turns earns a star in O(n + k).
Show hint
two running totals with the same remainder mod k differ by a multiple of k. Count how many running totals so far have each remainder. Watch out for negative remainders.