Subarray Sums Divisible by K

medium prefix sum hash map modular arithmetic

Problem

Given an integer array nums and an integer k, return the number of contiguous, non-empty subarrays that have a sum divisible by k.

Inputnums = [4, 5, 0, -2, -3, 1], k = 5

Output7

The 7 subarrays with a sum divisible by 5 include [5], [5, 0], [0], [5, 0, -2, -3], and others.

nums (comma-separated)

def subarrays_div_by_k(nums, k):
    counts = {0: 1}
    prefix = 0
    total = 0
    for x in nums:
        prefix += x
        r = prefix % k
        total += counts.get(r, 0)
        counts[r] = counts.get(r, 0) + 1
    return total

function subarraysDivByK(nums, k) {
  const counts = new Map([[0, 1]]);
  let prefix = 0, total = 0;
  for (const x of nums) {
    prefix += x;
    const r = ((prefix % k) + k) % k;
    total += counts.get(r) || 0;
    counts.set(r, (counts.get(r) || 0) + 1);
  }
  return total;
}

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> counts = new HashMap<>();
        counts.put(0, 1);
        int prefix = 0, total = 0;
        for (int x : nums) {
            prefix += x;
            int r = ((prefix % k) + k) % k;
            total += counts.getOrDefault(r, 0);
            counts.put(r, counts.getOrDefault(r, 0) + 1);
        }
        return total;
    }
}

int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> counts;
    counts[0] = 1;
    int prefix = 0, total = 0;
    for (int x : nums) {
        prefix += x;
        int r = ((prefix % k) + k) % k;
        total += counts[r];
        counts[r]++;
    }
    return total;
}

Explanation

A subarray's sum is divisible by k exactly when its two end prefix sums leave the same remainder mod k. So instead of summing every subarray, we track prefix-sum remainders and count matching pairs with a hash map.

We keep a running prefix and, at each step, compute r = prefix % k. Whenever the same remainder has been seen before, every earlier occurrence pairs with the current spot to form a subarray whose sum is divisible by k, so we add counts[r] to the total and then bump counts[r].

Negative numbers can make % return a negative value, so the language versions use ((prefix % k) + k) % k to fold the remainder into the 0..k-1 range. We seed the map with remainder 0 → 1 to catch subarrays that start at the very beginning.

Example: nums = [4,5,0,-2,-3,1], k = 5. Running remainders repeat enough times that the matched pairs add up to 7 qualifying subarrays, such as [5], [5,0], and [5,0,-2,-3].

One pass with constant-time map work gives O(n) time, and only k distinct remainders are ever stored, so O(k) space.

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