Divisible Subarray Sums — Solution & Editorial

Back to the Problem

Two prefixes with equal remainder mod K bound a divisible subarray: count pairs per remainder class with a frequency map (normalize negative remainders!).

Complexity: O(N)

Watch out: In C++/Java, (-3) % 5 = -3 — normalize to [0, K) or the map splits classes.