Problem Description

You are given an integer array nums and an integer k. Your task is to find the total number of non-empty subarrays whose sum is divisible by k.

A subarray is a contiguous sequence of elements from the array. For example, if nums = [1, 2, 3], then [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3] are all subarrays, but [1, 3] is not because the elements are not contiguous.

The sum of a subarray is divisible by k if the sum modulo k equals 0. In other words, if you add up all elements in the subarray and divide by k, the remainder should be 0.

The solution uses a clever approach with prefix sums and modular arithmetic. The key insight is that if two prefix sums have the same remainder when divided by k, then the subarray between them has a sum divisible by k.

Here's how it works:

• We maintain a running prefix sum s and calculate its modulo k at each step
• We use a hash table cnt to track how many times each remainder value has appeared
• When we encounter a remainder we've seen before, it means there are subarrays ending at the current position whose sum is divisible by k
• The number of such subarrays equals the count of that remainder we've seen so far
• We initialize cnt[0] = 1 to handle cases where the prefix sum itself is divisible by k

For each element, we update the prefix sum modulo k, add the count of matching remainders to our answer, then increment the count for the current remainder.

Intuition

The brute force approach would be to check every possible subarray and see if its sum is divisible by k. This would require O(n²) time to generate all subarrays and O(n) time to calculate each sum, resulting in O(n³) overall complexity. We need something more efficient.

Let's think about when a subarray sum is divisible by k. If we have a subarray from index i to j, its sum equals prefix_sum[j] - prefix_sum[i-1]. For this difference to be divisible by k, we need:

(prefix_sum[j] - prefix_sum[i-1]) % k = 0

This means: prefix_sum[j] % k = prefix_sum[i-1] % k

This is the key insight! Two prefix sums that have the same remainder when divided by k will create a subarray (between them) whose sum is divisible by k.

For example, if prefix_sum[3] = 17 and prefix_sum[7] = 32, and k = 5:

• 17 % 5 = 2
• 32 % 5 = 2
• The subarray sum from index 4 to 7 is 32 - 17 = 15, which is divisible by 5!

So instead of checking every subarray, we can:

1. Calculate the running prefix sum modulo k as we traverse the array
2. Keep track of how many times each remainder value has appeared
3. When we see a remainder we've encountered before, we know we can form subarrays ending at the current position that are divisible by k
4. The number of such subarrays equals how many times we've seen this remainder before

We initialize our counter with {0: 1} because an empty prefix (before any elements) has sum 0, which helps us count subarrays that start from index 0 and have sums divisible by k.

This transforms our problem from checking all subarrays to simply maintaining a frequency count of remainders, reducing time complexity to O(n).

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a hash table to count prefix sum remainders and a single pass through the array.

Data Structures Used:

• Hash table cnt to store the frequency of each remainder value
• Variable s to track the running prefix sum modulo k
• Variable ans to accumulate the result

Algorithm Steps:

1. Initialize the hash table: Start with cnt = {0: 1}. This represents that before processing any elements, we have one prefix sum of 0. This initialization handles cases where a prefix sum itself is divisible by k.

2. Initialize variables: Set ans = 0 (to count valid subarrays) and s = 0 (to track the running prefix sum).

3. Traverse the array: For each element x in nums:

   • Update prefix sum modulo k: Calculate s = (s + x) % k. This gives us the remainder of the current prefix sum when divided by k.

   • Count valid subarrays: Add cnt[s] to ans. This counts all previous prefix sums that have the same remainder, each forming a valid subarray ending at the current position.

   • Update the counter: Increment cnt[s] by 1 to record this new occurrence of remainder s.

4. Return the result: After processing all elements, ans contains the total count of subarrays divisible by k.

Handling Negative Numbers: In Python, the modulo operation handles negative numbers appropriately, but in some languages, you might need to adjust: if s becomes negative after the modulo operation, add k to it and take modulo again: s = ((s % k) + k) % k.

Time and Space Complexity:

• Time: O(n) where n is the length of the array, as we make a single pass
• Space: O(min(n, k)) for the hash table, which stores at most k different remainders

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

• Initial: cnt = {0: 1}, ans = 0, s = 0
• Process 4: s = 4, ans += cnt[4] = 0, cnt = {0: 1, 4: 1}
• Process 5: s = (4+5)%5 = 4, ans += cnt[4] = 1, cnt = {0: 1, 4: 2}
• Process 0: s = (4+0)%5 = 4, ans += cnt[4] = 3, cnt = {0: 1, 4: 3}
• And so on...

The algorithm efficiently counts all valid subarrays by leveraging the mathematical property that equal remainders indicate divisible subarray sums.

Example Walkthrough

Let's walk through a concrete example with nums = [2, 3, 5, 4, 1] and k = 5.

We want to find all subarrays whose sum is divisible by 5. Let me trace through the algorithm step by step:

Initial State:

• cnt = {0: 1} (we start with remainder 0 having count 1)
• ans = 0 (no valid subarrays found yet)
• s = 0 (prefix sum starts at 0)

Step 1: Process element 2

• Update prefix sum: s = (0 + 2) % 5 = 2
• Check cnt[2]: It doesn't exist yet, so cnt[2] = 0
• Update answer: ans = 0 + 0 = 0
• Update counter: cnt[2] = 1
• State: cnt = {0: 1, 2: 1}, ans = 0

Step 2: Process element 3

• Update prefix sum: s = (2 + 3) % 5 = 5 % 5 = 0
• Check cnt[0]: It exists with value 1
• Update answer: ans = 0 + 1 = 1 (Found subarray [2, 3] with sum 5)
• Update counter: cnt[0] = 2
• State: cnt = {0: 2, 2: 1}, ans = 1

Step 3: Process element 5

• Update prefix sum: s = (0 + 5) % 5 = 0
• Check cnt[0]: It exists with value 2
• Update answer: ans = 1 + 2 = 3 (Found subarrays [5] and [3, 5, ...] patterns)
• Update counter: cnt[0] = 3
• State: cnt = {0: 3, 2: 1}, ans = 3

Step 4: Process element 4

• Update prefix sum: s = (0 + 4) % 5 = 4
• Check cnt[4]: It doesn't exist yet, so cnt[4] = 0
• Update answer: ans = 3 + 0 = 3
• Update counter: cnt[4] = 1
• State: cnt = {0: 3, 2: 1, 4: 1}, ans = 3

Step 5: Process element 1

• Update prefix sum: s = (4 + 1) % 5 = 0
• Check cnt[0]: It exists with value 3
• Update answer: ans = 3 + 3 = 6 (Found subarrays ending at position 4)
• Update counter: cnt[0] = 4
• State: cnt = {0: 4, 2: 1, 4: 1}, ans = 6

Final Result: ans = 6

The 6 valid subarrays are:

1. [2, 3] (sum = 5)
2. [5] (sum = 5)
3. [2, 3, 5] (sum = 10)
4. [4, 1] (sum = 5)
5. [5, 4, 1] (sum = 10)
6. [2, 3, 5, 4, 1] (sum = 15)

The key insight demonstrated here is that whenever we encounter a remainder we've seen before (like remainder 0 appearing multiple times), it means we can form valid subarrays between those positions. The algorithm efficiently counts these without explicitly checking every possible subarray.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once, performing constant-time operations for each element (calculating the modulo, accessing and updating the counter, and adding to the answer).

The space complexity is O(min(n, k)). The Counter dictionary stores at most k different keys (since we're storing remainders modulo k, which can only be values from 0 to k-1). However, in the worst case where k > n, we would have at most n different remainders. Therefore, the space complexity is bounded by the minimum of n and k. When k is considered a constant or when k ≤ n, this simplifies to O(k) or O(n) respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Negative Numbers in Different Programming Languages

The most critical pitfall occurs when dealing with negative numbers and the modulo operation. In Python, the modulo operation % always returns a non-negative result when the divisor is positive, but this behavior varies across programming languages.

The Problem:

• In languages like Java, C++, and JavaScript, the modulo of a negative number can return a negative result
• For example, in Java: -1 % 5 returns -1, not 4 as in Python
• This breaks our algorithm because we expect remainders to be in the range [0, k-1]

Why It Matters: If we have a negative remainder like -2 and a positive remainder like 3 where k = 5, they should actually be treated as the same remainder class (since -2 ≡ 3 (mod 5)), but our hash table would treat them as different keys.

Solution: For languages other than Python, normalize the remainder to ensure it's always non-negative:

# Python handles this correctly, but for other languages:
def normalize_remainder(remainder, k):
    return ((remainder % k) + k) % k

# In the main loop:
prefix_sum = (prefix_sum + num) % k
if prefix_sum < 0:  # This check is unnecessary in Python but crucial in other languages
    prefix_sum = (prefix_sum + k) % k

2. Forgetting to Initialize the Counter with {0: 1}

The Problem: Omitting remainder_count = Counter({0: 1}) and starting with an empty counter would miss counting subarrays that start from the beginning of the array.

Why It Happens: When a prefix sum is divisible by k, its remainder is 0. Without the initial {0: 1}, we wouldn't count these valid subarrays.

Example: For nums = [5, 10] and k = 5:

• After processing 5: remainder is 0, but without initialization, remainder_count[0] would be 0, missing the subarray [5]
• After processing 10: cumulative sum is 15, remainder is 0, missing the subarray [5, 10]

Solution: Always initialize with {0: 1} to handle prefix sums that are themselves divisible by k.

3. Using Regular Dictionary Instead of Counter

The Problem: Using a regular dictionary and forgetting to check if a key exists before accessing it:

# Wrong approach that causes KeyError:
remainder_count = {0: 1}
for num in nums:
    prefix_sum = (prefix_sum + num) % k
    result += remainder_count[prefix_sum]  # KeyError if prefix_sum not in dictionary

Solution: Either use Counter from collections (which returns 0 for missing keys) or use the get() method:

# Option 1: Use Counter (recommended)
remainder_count = Counter({0: 1})

# Option 2: Use get() with default value
remainder_count = {0: 1}
result += remainder_count.get(prefix_sum, 0)

4. Integer Overflow in Other Languages

The Problem: In languages with fixed-size integers (like Java's int or C++'s int), the prefix sum might overflow for large arrays with large values.

Solution: Use appropriate data types:

• In Java: use long instead of int for the prefix sum
• In C++: use long long instead of int
• Python handles arbitrary precision integers automatically, so this isn't an issue

These pitfalls are especially important when translating the solution to different programming languages or when dealing with edge cases involving negative numbers or large values.