Count subarrays whose sum is divisible by k

Question

Given an integer array nums (values may be negative) and a positive integer k, count the number of contiguous subarrays whose sum is divisible by k. Target O(n) time.

Accepted Answer

Let P[i] be the running prefix sum. The subarray (j, i] has sum P[i] - P[j], which is divisible by k iff P[i] ≡ P[j] (mod k). So instead of storing prefix sums, store their remainders and count how many earlier prefixes had the same remainder as the current one. Seed the map with remainder 0 counted once, to catch subarrays starting at index 0. The one subtlety with negatives: -2 % 5 is 3 in Python, not -2, which is exactly the non-negative remainder we want, so no manual fix-up is needed. Trace nums = [4, 5, 0, -2, -3, 1], k = 5: prefix sums 4, 9, 9, 7, 4, 5 have remainders 4, 4, 4, 2, 4, 0.…

Count subarrays whose sum is divisible by k

Your answer

More Coding questions