Subarray Sums Divisible by K

In this problem, we are given an integer array nums and an integer k. Our task is to find the number of non-empty subarrays whose sum is divisible by k.

A subarray is simply a contiguous portion of the array. That means we only consider elements that are together in sequence.

Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: There are 7 subarrays whose sum is divisible by 5:

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Java Solution Using Prefix Sums and Modulo

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int prefix_mod = 0;
        int answer = 0;
        int[] mod_groups = new int[k];
        mod_groups[0] = 1;

        for (int num : nums) {
            prefix_mod = (prefix_mod + num % k + k) % k;
            answer += mod_groups[prefix_mod];
            mod_groups[prefix_mod]++;
        }

        return answer;
    }
}

Explanation

This problem is all about counting how many subarrays in the array nums have a sum that is divisible by k. But doing this naively—by checking all subarrays—would take too much time, especially for big arrays. So we need a smarter approach.

That’s where prefix sums and modular arithmetic come in.

What is a Prefix Sum?

A prefix sum is just the sum of the elements from the beginning of the array up to a certain point. For example, if nums = [4, 5], the prefix sums would be [4, 9]. We use prefix sums to help us calculate subarray sums quickly.

Key Insight Using Modulo

If the difference between two prefix sums is divisible by k, then the subarray between those two points is also divisible by k. In other words:

If prefixSum[i] % k == prefixSum[j] % k, then the sum of the subarray nums[j+1...i] is divisible by k.

What Are We Doing in the Code?

• We keep track of the current prefix sum modulo k using the variable prefix_mod.
• We store how many times each modulo value (from 0 to k−1) has occurred using the array mod_groups.
• Whenever we see a prefix sum modulo that we've seen before, it means there's at least one subarray between that point and now whose sum is divisible by k.

Step-by-Step Algorithm

1. Initialize Variables:
   • prefix_mod = 0: This tracks the running modulo of the prefix sum.
   • answer = 0: This counts how many valid subarrays we've found.
   • mod_groups[0] = 1: We set this because a sum divisible by k starting from index 0 is valid.
2. Iterate Through the Array:
   • For every element num, add it to prefix_mod and take modulo k.
   • Adjust for negatives by adding k before taking modulo again. This ensures we always get a positive remainder.
   • Increment answer by the number of times this particular prefix_mod has occurred so far. That means we found that many subarrays ending at the current index which have a sum divisible by k.
   • Increase the count for this prefix_mod in mod_groups.
3. Return the Answer: At the end, we return the value stored in answer.

Handling Negative Numbers

Java’s modulo operator can return negative values when the number is negative. That’s why we do:

(prefix_mod + num % k + k) % k

This ensures the result is always between 0 and k−1, no matter whether num is positive or negative.

Time and Space Complexity

• Time Complexity: O(n)
  • We only go through the array once. That makes it linear time.
• Space Complexity: O(k)
  • We use an array of size k to keep count of prefix mod values.

Example Dry Run

Let’s go through the input nums = [4,5,0,-2,-3,1] and k = 5 step-by-step.

Total valid subarrays: 7

Real-Life Analogy

Think of this like keeping track of how much money you've spent over time. If your spending increases and decreases, but every now and then it balances out to a full multiple of your budget limit (k), you count that as a “clean budget segment.” The trick is remembering where you had the same balance before, so you can calculate the span between those two points.

Conclusion

This is a beautiful problem that demonstrates the power of prefix sums and modular arithmetic. By using just one pass through the array and a simple map (or array), we can solve what initially seems like a tough problem with ease.

It’s efficient, clever, and teaches you the value of math-based patterns in programming. Whether you're preparing for interviews or just learning to code smarter, understanding this approach is a great milestone.

Happy Problem Solving!