1. Introduction

This problem asks you to count how many contiguous subarrays in an integer array have a sum divisible by a given integer K. The subarray must be continuous, and the sum must satisfy the condition:

(sum % K == 0)

Example inputs and outputs:

Input: nums = [4,5,0,-2,-3,1], K = 5
Output: 7

The challenge lies in doing this efficiently without checking every possible subarray, because the brute-force approach would be too slow for large inputs.

---

2. Understanding the Core Idea

A common technique for subarray sum problems is prefix sums. A prefix sum at index i represents the sum of all elements from index 0 to i.

Key observation:

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

Example:
If prefixSum[i] % K == prefixSum[j] % K,
then the subarray (j+1 … i) has a sum divisible by K.

This allows us to count valid subarrays by tracking how often each remainder appears.

---

3. Key Insight

To solve efficiently, we do the following:

1. Compute prefix sum cumulatively while iterating.
2. Take prefixSum % K at each step.
3. Normalize negative remainders (since modulo can be negative in Java).
4. Count how many times each remainder has occurred before, because each previous match contributes a valid subarray.
5. Use a frequency map or array to store remainder counts.

This reduces the solution to linear time.

---

4. Step-by-Step Algorithm

1. Initialize prefixSum = 0.
2. Initialize a frequency map that counts occurrences of remainders.
3. Seed the map with remainder 0 occurring once, because a prefix itself can be divisible by K.
4. For each number in the array:
   • Add the number to prefixSum.
   • Compute remainder = prefixSum % K.
   • If remainder is negative, add K to normalize.
   • The count of this remainder in the map indicates how many valid subarrays end here.
   • Add that count to the running answer.
   • Increment the frequency count for this remainder.
5. Return the total count.

---

5. Java Implementation

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int prefixSum = 0;
        int result = 0;

        int[] remainderCount = new int[k];
        remainderCount[0] = 1;

        for (int num : nums) {
            prefixSum += num;
            int remainder = prefixSum % k;

            if (remainder < 0) {
                remainder += k;
            }

            result += remainderCount[remainder];
            remainderCount[remainder]++;
        }

        return result;
    }
}

---

6. Time and Space Complexity

Time Complexity
O(n) — We process each element once and perform constant-time operations.

Space Complexity
O(K) — We store remainder frequencies up to K.

---

7. Detailed Dry Run Example

Example: nums = [4,5,0,-2,-3,1], K = 5

prefixSum = 0
remainderCount = [1,0,0,0,0]
result = 0

Element 4
prefixSum = 4
remainder = 4
result += remainderCount[4] → 0
remainderCount becomes [1,0,0,0,1]

Element 5
prefixSum = 9
remainder = 4
result += 1 → result = 1
remainderCount becomes [1,0,0,0,2]

Element 0
prefixSum = 9
remainder = 4
result += 2 → result = 3
remainderCount becomes [1,0,0,0,3]

Element -2
prefixSum = 7
remainder = 2
result += 0 → result = 3
remainderCount becomes [1,0,1,0,3]

Element -3
prefixSum = 4
remainder = 4
result += 3 → result = 6
remainderCount becomes [1,0,1,0,4]

Element 1
prefixSum = 5
remainder = 0
result += 1 → result = 7
remainderCount becomes [2,0,1,0,4]

Final answer: 7

---

8. Why the Approach Works

The method works because:

• Equal modulo values imply a divisible subarray
• Prefix sums allow tracking cumulative values without recomputation
• The remainder frequency map allows counting subarrays in constant time per step
• Negative numbers are handled safely through normalization
• It avoids the O(n²) brute-force approach entirely

---

9. Common Mistakes

• Attempting to check all subarrays manually, which leads to O(n²) time and fails for large input sizes.
• Forgetting to initialize the remainder count for zero, causing all prefix-only subarrays to be missed.
• Not normalizing negative remainders, which breaks correctness when the array contains negative values.
• Misinterpreting modulo behavior in Java, where negative sums yield negative remainders.
• Treating prefix sums as independent values rather than looking at modulo equivalence.