AlgoMaster Logo

Subarray Sums Divisible by K

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We need to count every contiguous subarray whose elements sum to a multiple of k. A sum is divisible by k when sum % k == 0, which includes negative sums like -5 being divisible by 5.

One way to solve this is to pick every possible start and end index, compute the sum, and check divisibility. With up to 30,000 elements, that O(n^2) work is on the edge of acceptable, so it helps to know there is a single-pass alternative.

That alternative comes from prefix sums. If two prefix sums leave the same remainder when divided by k, the subarray between those two positions has a sum divisible by k. If prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, and prefix[j] - prefix[i] is the sum of the subarray from index i+1 to j.

Key Constraints:

  • nums.length up to 3 * 10^4 → an O(n^2) scan does up to ~9 * 10^8 operations, borderline for the time limit. O(n) is the safe target.
  • nums[i] ranges from -10^4 to 10^4 → negative values force us to handle negative remainders. In Java, C++, Go, C#, and JavaScript, -7 % 5 gives -2, not 3.
  • k >= 2 → no division by zero or one.

Approach 1: Brute Force

Intuition

Try every possible subarray, compute its sum, and check if it is divisible by k. Maintaining a running sum keeps the inner loop O(1) per step instead of recomputing the sum from scratch.

For each starting index i, extend the subarray one element at a time, adding nums[j] to a running sum. Whenever that sum is divisible by k, increment the count.

Algorithm

  1. Initialize a counter count to 0
  2. For each starting index i from 0 to n - 1:
    • Initialize sum to 0
    • For each ending index j from i to n - 1:
      • Add nums[j] to sum
      • If sum % k == 0, increment count
  3. Return count

Example Walkthrough

1i=0: sums 4,9,9,7,4,5. Only 5%5==0. count=1
0
i
4
1
5
2
0
3
-2
4
-3
5
1
1/6

Code

The next approach replaces the per-pair check with a property of remainders that counts all valid subarrays in a single pass.

Approach 2: Prefix Sum + Hash Map (Optimal)

Intuition

Let prefix[j] be the sum of nums[0..j-1]. The sum of any subarray nums[i..j] equals prefix[j+1] - prefix[i].

We want (prefix[j+1] - prefix[i]) % k == 0. In modular arithmetic, that holds exactly when prefix[j+1] % k == prefix[i] % k. Two prefix sums with the same remainder mod k define a subarray whose sum is divisible by k.

The problem reduces to counting how many pairs of prefix sums share the same remainder.

This takes one pass. As we compute the running prefix sum, we track its remainder prefix % k and keep a hash map of how many times each remainder has appeared so far. When the current remainder has been seen m times before, those are m previous prefix sums with the same remainder, which give m new valid subarrays ending at the current position.

Negative numbers need care. In Java, C++, Go, C#, and JavaScript, the % operator can return a negative result for negative operands. For example, -7 % 5 = -2 in Java, but the remainder we want is 3 (since -7 = -2 * 5 + 3). Normalizing with ((prefix % k) + k) % k maps the remainder back into the range 0 to k-1. Python's % already returns a non-negative result for positive k, so it needs no adjustment.

Algorithm

  1. Initialize a hash map remainderCount with {0: 1} (a prefix sum of 0 has remainder 0, and it exists once before we start)
  2. Initialize prefixSum = 0 and count = 0
  3. For each element num in nums:
    • Add num to prefixSum
    • Compute the non-negative remainder: remainder = ((prefixSum % k) + k) % k
    • If remainder exists in remainderCount, add its value to count (each previous occurrence is a valid subarray)
    • Increment remainderCount[remainder] by 1
  4. Return count

Example Walkthrough

nums
1Init: prefixSum=0, count=0, remainderCount={0:1}
0
4
i
1
5
2
0
3
-2
4
-3
5
1
remainderCount
1Init: prefixSum=0, count=0, remainderCount={0:1}
{0: 1}
1/8

Code