Subarray Sums Divisible by K

How it works

Since remainders when dividing by k are always in the range [0, k-1], we can use a fixed-size array instead of a hash map. This gives slightly better constant factors. We also handle negative numbers by adding k to the modulo result, ensuring all remainders are non-negative.

Steps

1. Create an array count of size k, initialized to zeros, with count[0] = 1.
2. Initialize prefix = 0 and res = 0.
3. For each number in the array:
   • Update prefix = (prefix + num % k + k) % k to handle negatives.
   • Add count[prefix] to res.
   • Increment count[prefix].
4. Return res.

Complexity

• Time complexity: O(n + k)
• Space complexity: O(k)

Things to watch for

Mishandling Negative Remainders

In most programming languages, the modulo of a negative number can return a negative result (e.g., -5 % 3 = -2 in Java/C++). You must normalize the remainder to be non-negative by using ((prefixSum % k) + k) % k to ensure correct hash map lookups.

Confusing This Problem with Subarray Sum Equals K

While both problems use prefix sums, the comparison logic differs. Here you need to match remainders, not exact differences. Two prefix sums with the same remainder modulo k indicate a valid subarray, regardless of their absolute values.

Forgetting to Initialize Count for Remainder Zero

The hash map or array must start with count[0] = 1 to account for subarrays starting from index 0 that are directly divisible by k. Missing this initialization causes undercounting.

from typing import List

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        count = [0] * k
        count[0] = 1
        prefix = res = 0

        for num in nums:
            prefix = (prefix + num + k) % k
            res += count[prefix]
            count[prefix] += 1

        return res

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        vector<int> count(k, 0);
        count[0] = 1;
        int prefix = 0, res = 0;

        for (int num : nums) {
            prefix = (prefix + num % k + k) % k;
            res += count[prefix];
            count[prefix]++;
        }

        return res;
    }
};