Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumprefix-sum

Subarray Sums Divisible by K

Problem (restated)

Return the number of non-empty subarrays whose sum is divisible by k.

Intuition

Same remainder of prefix sums ⇒ between-sum divisible by k.

Approaches

Prefix mod counts

Unverified

Time O(n)Space O(k)

Idea. Count frequency of each prefix mod; for each new mod r, add count[r] then increment.

Walkthrough. [4,5,0,-2,-3,1], k=5 → 7.

Trade-offs. Normalize negative mods in languages with negative remainder.

Solution

export function subarraysDivByK(nums: number[], k: number): number {
  const cnt = new Array<number>(k).fill(0);
  cnt[0] = 1;
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    const r = ((sum % k) + k) % k;
    ans += cnt[r]!;
    cnt[r]!++;
  }
  return ans;
}

export function subarraysDivByK(nums: number[], k: number): number {
  const cnt = new Array<number>(k).fill(0);
  cnt[0] = 1;
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    const r = ((sum % k) + k) % k;
    ans += cnt[r]!;
    cnt[r]!++;
  }
  return ans;
}

Template connection

Prefix sums modulo k; count remainder frequencies (same family as 523 / 930).

Reflection

Earlier prefixes with the same pref % k each close a qualifying subarray. Negatives: normalize with ((pref % k) + k) % k so C# and TypeScript match Python.
Seed the empty prefix as mod 0 once. A subarray cannot be empty. How does that seed avoid counting an empty one?
k = 1: every subarray qualifies, so the answer is n * (n + 1) / 2.