Subarray Sums Divisible by k

Tips

题目类型: 前缀和

Problem

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

A subarray is a contiguous part of an array.

Constraints:

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

Examples

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Input: nums = [5], k = 9
Output: 0

Solution

This problem is very similar to 560. Subarray Sum Equals k. The r difference is that we're looking for subarrays whose sum is divisible by k, rather than equal to k.

Key Insight:

If two prefix sums have the same remainder when divided by k, then the subarray between them has a sum divisible by k.

Why?

If preSum[i] % k = r and preSum[j] % k = r (where j > i)
Then (preSum[j] - preSum[i]) % k = 0
This means the subarray from i+1 to j has sum divisible by k

Important Detail:

We need to handle negative remainders correctly using: r = ((preSum % k) + k) % k

This ensures the remainder is always non-negative (0 to k-1).

Algorithm:

Initialize a HashMap with {0: 1} (base case: empty prefix has remainder 0)
Iterate through the array:
- Calculate running prefix sum
- Calculate remainder: r = ((preSum % k) + k) % k
- If this remainder exists in the map, add its frequency to count
- Update the frequency of this remainder in the map
Return the total count

Time Complexity: O(n) - single pass through the array Space Complexity: O(k) - at most k different remainders in the HashMap

function subarraysDivByK(nums: number[], k: number): number {
  const map = new Map([[0, 1]]) // Initialize with remainder 0
  let preSum = 0
  let count = 0

  for (const num of nums) {
    preSum += num
    // Ensure remainder is non-negative
    const r = ((preSum % k) + k) % k

    if (map.has(r)) {
      count += map.get(r)
    }

    map.set(r, (map.get(r) || 0) + 1)
  }

  return count
}

Example walkthrough:

For nums = [4, 5, 0, -2, -3, 1], k = 5:

Initial: map = {0: 1}, preSum = 0, count = 0

i=0, num=4:
  preSum = 4, r = 4 % 5 = 4
  map = {0: 1, 4: 1}

i=1, num=5:
  preSum = 9, r = 9 % 5 = 4
  4 exists! count += 1 (found [5])
  map = {0: 1, 4: 2}

i=2, num=0:
  preSum = 9, r = 9 % 5 = 4
  4 exists! count += 2 (found [5,0] and [4,5,0])
  map = {0: 1, 4: 3}

... (continues)

Result: count = 7

Problem​

Solution​

Problem

Solution