Subarray sums divisible by K

Count the contiguous subarrays whose sum is a multiple of k. Two prefix sums with the same remainder mod k enclose exactly such a subarray, so count remainders as you go.

The idea

The sum of nums[j + 1..i] is prefix[i] - prefix[j]. That difference is a multiple of k exactly when prefix[i] and prefix[j] leave the same remainder mod k. So walk the array keeping the running sum, and at each step add how many earlier prefixes had the same remainder. Counting by remainder needs only k counters.

Code

public int SubarraysDivByK(int[] nums, int k) {
    var count = new int[k]; // count[r] = prefixes seen with remainder r
    count[0] = 1; // the empty prefix: sum 0, remainder 0
    int sum = 0, result = 0;
    foreach (int x in nums) {
        sum += x;
        int r = sum % k;
        if (r < 0) r += k; // C# % keeps the sign of sum: shift -1 up to k - 1
        result += count[r]; // each earlier prefix with remainder r starts a valid subarray
        count[r]++;
    }
    return result;
}

Tips

• count[0] = 1 stands for the empty prefix before index 0, so a subarray starting at index 0 whose sum is a multiple of k is counted.
• Negative sums need the fix: in C#, -4 % 3 is -1, not 2. Both mean "1 below a multiple of 3", so add k to land in 0..k - 1. Without it, -1 and 2 would be counted as different remainders.
• Same shape as subarray sum equals k, with the remainder in place of the sum as the dictionary key.

In the .NET library

C# % is a remainder, not a modulo: its result has the sign of the left operand. ((sum % k) + k) % k is the branch-free form of the same fix.