Subarray Sums Divisible by K

Intuition

The sum of the subarray from index i to j equals prefix[j] - prefix[i - 1]. That difference is divisible by k exactly when prefix[j] and prefix[i - 1] leave the same remainder modulo k, because their difference then clears out to a multiple of k. So instead of tracking exact prefix sums, we only need their remainders. We keep a frequency table of how many earlier prefixes produced each remainder; whenever we reach a remainder we have seen before, each earlier occurrence forms a valid subarray with the current position. Negative sums must be normalized with ((r % k) + k) % k so that, for example, -1 and k - 1 land in the same bucket. Seeding remainder 0 with a count of one accounts for prefixes that are themselves divisible by k.

Algorithm walkthrough

1. 1Create a frequency array (or map) of size k, initialize it so remainder 0 has count 1, and set the running sum and answer to 0.
2. 2Walk through nums, adding each value to the running sum.
3. 3Compute the normalized remainder r = ((running % k) + k) % k so negative running sums map into [0, k).
4. 4Add the current count of remainder r to the answer, since each earlier prefix with the same remainder marks a divisible subarray, then increment the count of r.
5. 5After the pass, the accumulated answer is the number of subarrays whose sum is divisible by k.

Implementation

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        counts = [0] * k
        counts[0] = 1
        running = 0
        answer = 0
        for num in nums:
            running += num
            r = ((running % k) + k) % k
            answer += counts[r]
            counts[r] += 1
        return answer