Subarray Sum Divisible by K — Prefix Mod HashMap

Problem 197 · Subarray Sum Divisible by K

Difficulty: Medium · Pattern: Prefix Mod + HashMap

Count subarrays with sum divisible by k.

Intuition

If prefix[j] % k == prefix[i] % k, the subarray sum between i+1 and j is divisible by k. Track prefix mod frequencies.

Solutions

# Python
from collections import defaultdict
def subarraysDivByK(nums, k):
    cnt = defaultdict(int)
    cnt[0] = 1
    prefix = 0; ans = 0
    for x in nums:
        prefix = (prefix + x) % k
        ans += cnt[prefix]
        cnt[prefix] += 1
    return ans

// Java
public int subarraysDivByK(int[] nums, int k) {
    Map<Integer,Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int prefix = 0, ans = 0;
    for (int x : nums) {
        prefix = ((prefix + x) % k + k) % k;
        ans += cnt.getOrDefault(prefix, 0);
        cnt.merge(prefix, 1, Integer::sum);
    }
    return ans;
}

// C++
int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int,int> cnt; cnt[0]=1;
    int prefix=0, ans=0;
    for (int x : nums) {
        prefix = ((prefix+x)%k+k)%k;
        ans += cnt[prefix];
        cnt[prefix]++;
    }
    return ans;
}

Complexity

Time: O(n)
Space: O(k)

Edge Case

Use ((prefix+x)%k+k)%k to handle negative numbers.