[Prefix Sum] Subarray Sums Divisible by K

[sudosf]

Problem

Given an integer array and k, return the number of non-empty subarrays that have a sum divisible by k.

References

• LeetCode: https://leetcode.com/problems/subarray-sums-divisible-by-k/
• GFG: https://www.geeksforgeeks.org/problems/sub-array-sum-divisible-by-k2617/1
• Sheet: https://www.risingbrain.org/sheet#array (Prefix Sum [Two Pointer] 3Sum #6)
• Parent: Pattern: Prefix Sum (Arrays) #51

Difficulty

🟡 Medium

Companies

Goldman Sachs, Microsoft, PayPal

Notes

Language: Java
Same mod-map pattern as Continuous Subarray Sum but counting all occurrences. Handle negative remainders in Java with ((sum % k) + k) % k.