#974 Subarray Sums Divisible by K
the problem
In plain words
Return the number of non-empty contiguous subarrays whose sum is divisible by k. Values can be negative.
in nums = [4,5,0,-2,-3,1], k = 5
out 7
in nums = [5], k = 9
out 0
- 1 ≤ n ≤ 3·10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- 2 ≤ k ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix sum + HashMap
sum(j..i) is divisible by k iff P[i+1] and P[j] leave the same remainder mod k. So count equal remainders, just like Subarray Sum Equals K.
solutions
From brute force to optimal
Check sum % k == 0 for every subarray.
- For each start, extend end, test the running sum.
All pairs, about 4.5·10⁸ for n = 3·10⁴: too slow.
A running sum.
class Solution { public int subarraysDivByK(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; if (sum % k == 0) count++; // -5 % 5 == 0 too, so negatives are fine here } } return count; }}Map remainder → count of prefixes with it; add the count before incrementing.
- seen = {0: 1}.
- rem = floorMod(sum, k).
- count += seen[rem]; seen[rem]++.
One pass, O(1)-average map work.
At most k distinct remainders.
class Solution { public int subarraysDivByK(int[] nums, int k) { Map<Integer, Integer> seen = new HashMap<>(); // remainder → how many prefixes had it seen.put(0, 1); int sum = 0, count = 0; for (int x : nums) { sum += x; int rem = Math.floorMod(sum, k); // always 0..k-1, even for negative sums count += seen.getOrDefault(rem, 0); seen.merge(rem, 1, Integer::sum); } return count; }}Remainders are 0..k−1, so an array is a perfect hash table. Keep only the remainder, so nothing can overflow.
- seen = new int[k]; seen[0] = 1.
- rem = ((rem + x) % k + k) % k.
- count += seen[rem]++.
One pass, array access only.
k counters.
class Solution { public int subarraysDivByK(int[] nums, int k) { int[] seen = new int[k]; // remainders are 0..k-1 → an array is a perfect hash table seen[0] = 1; int rem = 0, count = 0; for (int x : nums) { rem = ((rem + x) % k + k) % k; // keep only the remainder: no overflow, never negative count += seen[rem]; seen[rem]++; } return count; }}in the room
How to say it in the interview
talk track
- Connect it to LC 560: "same idea, but the key is the remainder."
- Call out Java's negative
%and fix it with floorMod.
traps
sum % kis negative for negative sums in Java, so −1 and 4 (mod 5) land in different keys. Normalise the remainder.
what they ask next
Follow-ups
Continuous Subarray Sum (LC 523): length ≥ 2 and a multiple of k?
Map remainder → first index; a hit with i − first ≥ 2 means yes.
before you submit
Edge cases to test
- Negative numbers: Java's % can be negative — normalise with Math.floorMod.
- Zeros: [0,0] with k = 3 → 3.
- No valid subarray ([5], k = 9) → 0.
practise next
Similar problems
- #560Subarray Sum Equals KMediumin Hashing
- #525Contiguous ArrayMediumin Hashing