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

Tested only

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;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?