Subarrays Divisible by K (K-Subarrays)

A portfolio risk monitoring system at Citadel analyzes an array of integer portfolio returns nums. A contiguous sequence of trading intervals (a subarray) is deemed an order execution cluster if the sum of returns is evenly divisible by a risk parameter $k$ ($sum \bmod k == 0$).

Your Task

Implement subarrays_div_by_k(nums: list[int], k: int) -> int that returns the count of non-empty contiguous subarrays whose sum is divisible by $k$ in $\mathcal{O}(N)$ time.

Constraints

• $1 \le \text{len}(nums) \le 3 \times 10^4$
• $-10^4 \le nums[i] \le 10^4$
• $2 \le k \le 10^4$

Examples

nums = [4, 5, 0, -2, -3, 1]
k = 5
# Subarrays divisible by 5 include:
# [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3], [4, 5, 0, -2, -3, 1]
# Total: 7
# Output: 7