Subarray Sums Divisible by K

Problem Statement

The task is to count the number of contiguous subarrays within an integer array nums, where the sum of the elements in the subarray is divisible by a given integer k. The elements in the array, as well as the subarrays derived from it, can take on any integer value, positive or negative. Understanding that a "subarray" refers to a sequence of one or more elements that are contiguous segments of the main array, the solution should efficiently determine the count of such subarrays where the sum meets the divisibility criterion.

Examples

Example 1

Input:

nums = [4,5,0,-2,-3,1], k = 5

Output:

7

Explanation:

There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2

Input:

nums = [5], k = 9

Output:

0

Constraints

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

Approach and Intuition

The problem can be approached by focusing on the sum of subarrays and checking for divisibility by k. Here's the step-by-step plan:

1. Utilize a Hash Map for Frequency Count of Remainders: As you iterate through the array, for each element, maintain a cumulative sum. For each new cumulative sum, compute the remainder of this sum when divided by k. Store and update the frequency of each unique remainder in a hash map.

2. Understanding Remainder Behavior: The remainder, when divided by k, could potentially be negative (if the numbers in nums are negative and k is positive, for example). Volatility in remainder signs can be normalized by adjusting remainders: if a remainder is negative, simply add k to it to make it positive.

3. Leverage the Pigeonhole and Prefix Sum Principle: The primary insight here leans on the idea of prefix sums. Specifically, if two prefix sums yield the same remainder upon division by k, then the elements lying between these two prefixes sum up to some multiple of k (hence, are divisible by k).

4. Count Potential Subarrays: Every time a remainder repeats, it means there are multiple subarrays (ending at different indices) which have sums divisible by k. Use the hash map to count these occurrences. For each remainder, if it has been seen n times before, then there are n subarrays ending at the current index that can be formed which have sums divisible by k.

This approach capitalizes on both the properties of remainders and the utility of hash maps for efficient frequency counts, ensuring that each subarray is checked for divisibility without explicitly computing the sum for every possible subarray, thereby improving efficiency.

Solutions

class Solution {
public:
    int subarraysWithSumDivisibleByK(vector<int>& array, int divisor) {
        int length = array.size();
        int currentMod = 0, totalCount = 0;
    
        vector<int> remainderCount(divisor);
        remainderCount[0] = 1;
    
        for (int element : array) {
            currentMod = (currentMod + element % divisor + divisor) % divisor;
            totalCount += remainderCount[currentMod];
            remainderCount[currentMod]++;
        }
    
        return totalCount;
    }
};