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.

The brute force way to think about it: pick every possible start and end index, compute the sum, and check divisibility. But with up to 30,000 elements, that O(n^2) or O(n^3) approach might be tight. The real question is whether we can do this in a single pass.

The key observation is that this is a prefix sum problem in disguise. If two prefix sums have the same remainder when divided by k, then the subarray between those two positions has a sum divisible by k. Why? Because if prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, and prefix[j] - prefix[i] is exactly the sum of the subarray from index i+1 to j.

Key Constraints:

nums.length up to 3 * 10^4 → O(n^2) might pass but is borderline. O(n) is ideal.
nums[i] ranges from -10^4 to 10^4 → Negative values mean we need to handle negative remainders carefully. In most languages, -7 % 5 gives -2, not 3.
k >= 2 → We never divide by zero or one, which simplifies things.

Approach 1: Brute Force

Intuition

The most straightforward way: try every possible subarray, compute its sum, and check if it's divisible by k. We can optimize the inner loop slightly by maintaining a running sum instead of recomputing from scratch each time.

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

Algorithm

Initialize a counter count to 0
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

Return count

Example Walkthrough

1i=0: sums 4,9,9,7,4,5. Only 5%5==0. count=1

-2

-3

1/6

Code

Complexity Analysis

Time Complexity: O(n^2). Two nested loops, each running up to n times. For each starting index, we scan the rest of the array.
Space Complexity: O(1). We only use a few variables regardless of input size.

The brute force checks every subarray individually. What if instead of checking every pair of endpoints, we could use the mathematical property of remainders to count all valid subarrays in a single pass?

Approach 2: Prefix Sum + Hash Map (Optimal)

Intuition

Here's the mathematical insight that makes this problem elegant. 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. By the properties of modular arithmetic, this happens exactly when prefix[j+1] % k == prefix[i] % k. In other words, two prefix sums with the same remainder mod k define a subarray whose sum is divisible by k.

So the problem reduces to: how many pairs of prefix sums share the same remainder?

We can solve this in one pass. As we compute the running prefix sum, we track the remainder prefix % k and keep a count of how many times each remainder has appeared so far in a hash map. When we encounter a remainder that we've seen m times before, that means there are m previous prefix sums with the same remainder, giving us m new valid subarrays ending at the current position.

There's one subtle gotcha: negative numbers. In languages like Java, C++, Go, and JavaScript, the % operator can return negative results for negative operands. For example, -7 % 5 = -2 in Java, but mathematically we want the remainder to be 3 (since -7 = -2 \* 5 + 3). The fix is simple: use ((prefix % k) + k) % k to normalize the remainder to a non-negative value. Python's % operator already handles this correctly, always returning a non-negative result.

Why does this work?

The technique rests on a simple property of modular arithmetic: if a % k == b % k, then (a - b) % k == 0. Applied to prefix sums, this means any two prefix sums with the same remainder define a subarray whose sum is divisible by k.

By initializing the map with {0: 1}, we handle the case where a prefix sum itself is divisible by k (the subarray starts at index 0). The counting step count += remainderCount[remainder] works because if we've seen a remainder m times before, each of those m previous positions pairs with the current position to form a valid subarray.

Algorithm

Initialize a hash map remainderCount with {0: 1} (a prefix sum of 0 has remainder 0, and it exists once before we start)
Initialize prefixSum = 0 and count = 0
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

Return count

Example Walkthrough

nums

1Init: prefixSum=0, count=0, remainderCount={0:1}

-2

-3

remainderCount

1Init: prefixSum=0, count=0, remainderCount={0:1}

{0: 1}

1/8

Code

Complexity Analysis

Time Complexity: O(n). We iterate through the array once. Each step involves a constant-time hash map lookup and insertion.
Space Complexity: O(min(n, k)). The hash map stores at most k distinct remainders (0 through k-1). In practice, it stores at most min(n+1, k) entries.

Subarray Sums Divisible by K

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Prefix Sum + Hash Map (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium