Introduction

The efficient way to count subarrays whose sum is divisible by k is to use prefix sums and remainder frequencies. The key observation is that if two prefix sums leave the same remainder when divided by k, then the subarray between them has a sum divisible by k.

The Core Observation

Let prefix[i] be the sum of the first i elements. A subarray from l to r has sum:

prefix[r + 1] - prefix[l]

This subarray is divisible by k exactly when those two prefix sums have the same remainder modulo k.

So instead of checking every subarray directly, we count how often each remainder has already appeared.

The O(n) Algorithm

The algorithm is:

1. keep a running prefix sum
2. compute its remainder modulo k
3. if that remainder has appeared before, add its frequency to the answer
4. record the current remainder in the frequency map

Initialize the map with remainder 0 seen once, because a prefix sum already divisible by k forms a valid subarray from the beginning.

Python Implementation

1from collections import defaultdict
2
3
4def subarrays_div_by_k(nums, k):
5    count = 0
6    prefix = 0
7    freq = defaultdict(int)
8    freq[0] = 1
9
10    for num in nums:
11        prefix += num
12        remainder = prefix % k
13        count += freq[remainder]
14        freq[remainder] += 1
15
16    return count
17
18
19print(subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5))

This returns 7, which is the standard result for that example.

Why It Works

Suppose the current prefix remainder is r, and you have already seen r three times earlier. Each earlier occurrence represents one starting point that forms a subarray ending at the current index with sum divisible by k.

So every time you see a remainder again, you instantly know how many new valid subarrays were created.

That is what collapses the naive quadratic search into a linear pass.

Handling Negative Numbers

Negative numbers do not break the idea. The only subtle point is modulo behavior.

In Python, % already gives a nonnegative remainder when k is positive, so the implementation above works directly.

In some other languages, the remainder may be negative. In those languages, a common normalization is:

remainder = ((prefix % k) + k) % k;

That keeps remainder keys consistent.

Compare with the Naive Solution

The brute-force approach checks all subarrays and computes or updates their sums, which takes O(n^2) time even with prefix sums.

The optimized prefix-remainder method uses:

• one pass through the array
• constant-time hashmap operations

So the total time is O(n), with O(k) or O(n) auxiliary space depending on how many distinct remainders appear.

A Small Walkthrough

For nums = [4, 5, 0, -2, -3, 1] and k = 5, the running remainders are:

• after 4: remainder 4
• after 9: remainder 4
• after 9: remainder 4
• after 7: remainder 2
• after 4: remainder 4
• after 5: remainder 0

Repeated remainders create valid subarrays. That is why the count increases whenever a remainder appears again.

Common Pitfalls

Forgetting to initialize remainder 0 with frequency 1 causes subarrays starting at index 0 to be missed.

Using the raw modulo result in languages with negative remainder behavior can produce wrong counts when the array contains negative values.

Trying to solve the problem by testing every subarray is unnecessarily slow once n gets large.

Finally, do not confuse "sum divisible by k" with "every element divisible by k". The property applies to the subarray sum, not to individual entries.

Summary

• use prefix sums and remainder frequencies to count valid subarrays in linear time
• two prefix sums with the same remainder modulo k define a subarray whose sum is divisible by k
• initialize remainder 0 once to count subarrays that start at the beginning
• normalize negative remainders in languages where % can return a negative value
• the optimal standard solution is O(n) time, far better than checking every subarray explicitly