Subarray Sums Divisible by K (Prefix Remainder Counting)

• This problem counts subarrays whose sum is a multiple of k, in an array with possible negatives.
• A subarray sum is divisible by k when the two bounding prefix sums share the same remainder mod k.
• Track remainders in a frequency array of size k, incrementing at each step.
• Normalize negative remainders: r = ((prefix % k) + k) % k.
• Seed remainder 0 with count 1 for the empty prefix.
• Time is O(N) and space is O(k).

What is the Subarray Sums Divisible by K problem?

Given an array of integers and a positive integer k, count the number of contiguous subarrays whose sum is divisible by k. This is LeetCode 974.

For example, given [4, 5, 0, -2, -3, 1] and k = 5, the answer is 7.

Why do equal remainders mean divisibility?

From modular arithmetic: a subarray from j+1 to i has sum prefix[i] - prefix[j]. This difference is divisible by k exactly when prefix[i] and prefix[j] leave the same remainder when divided by k, because (a - b) % k == 0 when a % k == b % k.

How does the algorithm work?

package com.bank.service;

public class SubarrayDivisibleKService {

    /**
     * Counts settlement stretches divisible by the clearing unit.
     * Used by the National Bank of India batch-settlement team.
     */
    public static int subarraysDivByK(int[] flows, int k) {
        int[] remainderCount = new int[k];
        remainderCount[0] = 1; // Seed: empty prefix has remainder 0

        long prefix = 0;
        int count = 0;

        for (int flow : flows) {
            prefix += flow;
            int r = (int) (((prefix % k) + k) % k); // Normalize
            count += remainderCount[r]; // Pairs with same remainder
            remainderCount[r]++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] flows = {4000, 5000, 0, -2000, -3000, 1000};
        int k = 5000;
        System.out.println("Stretches divisible by " + k
            + ": " + subarraysDivByK(flows, k));
    }
}

javac -d out com/bank/service/SubarrayDivisibleKService.java
java -cp out com.bank.service.SubarrayDivisibleKService

Stretches divisible by 5000: 7

Why is remainder normalization critical?

In Java, the % operator can return a negative result for negative operands. For example, -2 % 5 gives -2 rather than 3. Since remainders must be compared consistently, we normalize with ((prefix % k) + k) % k to ensure the remainder is always in [0, k-1]. Without normalization, congruent prefixes of opposite sign would land in different buckets.

// WRONG: negative remainder
long prefix = -7;
int r = (int) (prefix % 5); // r = -2, but should be 3

// CORRECT: normalized remainder
int r = (int) (((prefix % 5) + 5) % 5); // r = 3

Why use an int[k] array instead of a HashMap?

Since k is bounded and remainders are integers in [0, k-1], a plain int[k] array is faster than a HashMap. It avoids boxing, hashing, and auto-resizing overhead. For small k values this makes a noticeable difference in tight loops.

What are the edge cases?

Several edge cases require attention.

• k = 1: every subarray sum is divisible by 1, giving N*(N+1)/2 subarrays.
• All zeros: every subarray has sum 0, which is divisible by any k.
• Negative elements: handled by the remainder normalization.
• Single element divisible by k: counted via the seed.

package com.bank.core;

public class DivisibleEdgeCases {
    public static void main(String[] args) {
        // k = 1: all subarrays qualify
        System.out.println(divByK(new int[]{1, 2, 3}, 1)); // 6

        // All zeros
        System.out.println(divByK(new int[]{0, 0, 0}, 5)); // 6

        // Negative elements
        System.out.println(divByK(new int[]{-5, 10, -5}, 5)); // 6
    }

    static int divByK(int[] arr, int k) {
        int[] rc = new int[k]; rc[0] = 1; long pre = 0; int cnt = 0;
        for (int a : arr) { pre += a; int r = (int)(((pre % k) + k) % k); cnt += rc[r]; rc[r]++; }
        return cnt;
    }
}

6
6
6

What is the time and space complexity?

Time is O(N): one pass with constant-time remainder work per element. Space is O(k) for the remainder frequency array. When k is small relative to N, this is very space-efficient.

How is this related to Subarray Sum Equals K?

Both use the prefix-sum family. The key difference is what we track.

| Problem | Track in map/array | Match condition |
|---|---|---|
| Sum = k | Exact prefix value | prefix[i] - prefix[j] = k |
| Sum divisible by k | Prefix mod k | prefix[i] mod k = prefix[j] mod k |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Remainder normalization is the signature detail: it is the single correctness issue specific to the divisibility variant.
• Combinatorial interpretation: if a remainder appears c times, the number of pairs is c * (c-1) / 2. You can compute the count this way after the scan instead of incrementally.
• Overflow: prefix sums can overflow int on long financial sequences. Use long for the prefix.
• Generalization: subarray sum with remainder r mod k requires tracking the same remainder structure with a target offset.