Prefix Sum — Subarray Sums Divisible by K

↗ LeetCode: Subarray Sums Divisible by K · Medium · pattern chapter →

Asked atGoogleAmazon

Count subarrays whose sum is divisible by k.

Example 1 — nums = [4,5,0,-2,-3,1], k = 5 → 7Example 2 — nums = [5], k = 9 → 0Example 3 — nums = [-1,2,9], k = 2 → 2

Constraints — 1 ≤ n ≤ 3·10⁴; 2 ≤ k ≤ 10⁴. Brute checks every subarray — O(n²) = 10¹⁰ ops at n=3·10⁴ (TLE). Prefix sum + hashmap of remainders is O(n) = 3·10⁴ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Every subarray

O(n²) sums. Baseline.

Approach 2 — Prefix sum modulo k with hash map

Insight. Two prefix sums with the same remainder mod k → their difference is divisible by k. Count pairs of prefixes sharing each remainder.

Trap — Java % can be negative. Use ((sum % k) + k) % k.

int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int pref = 0, res = 0;
    for (int x : nums) {
        pref += x;
        int m = ((pref % k) + k) % k;
        res += cnt.getOrDefault(m, 0);
        cnt.merge(m, 1, Integer::sum);
    }
    return res;
}

Execution Trace

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

Step 1 / 4first prefix

Complexity — Time O(n); Space O(k).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Brute	O(n²)	O(1)	baseline
Prefix mod + map	O(n)	O(k)	optimum

When to use which

• "Sum divisible by k" → prefix mod + hash map (initialise with {0:1}).
• Negatives possible → the ((% + k) % k) normalization is required.
• "Longest / shortest such subarray" → change map to store first-index; take max/min index difference.

✨AI Study CompanionBeta

Related problems

• Subarray Sum Equals K
• Continuous Subarray Sum — sum multiple of k with length ≥ 2
• Contiguous Array — same modulo trick with +1/−1

Was this page helpful?

📚 Related problems

• → Prefix Sum Subarray Sum Equals K
• → Continuous Subarray Sum
• → Car Pooling