Subarray Sums Divisible by K
Problem
Return the number of non-empty contiguous subarrays whose sum is divisible by k. Values can be negative.
Example 1
Input: nums = [4, 5, 0, -2, -3, 1], k = 5 Output: 7
Test cases
Case 1
Input: [4,5,0,-2,-3,1], 5 Expected: 7
Case 2
Input: [5], 9 Expected: 0
Case 3
Input: [5,10], 5 Expected: 3
View solutionHide solution1 approach
1. Count prefix remainders
Time O(n)Space O(k)
Every pair of equal prefix remainders is one valid subarray. Normalise negative remainders with ((x % k) + k) % k.
function subarraysDivByK(nums, k) { const cnt = new Array(k).fill(0); cnt[0] = 1; let sum = 0, res = 0; for (const x of nums) { sum = (((sum + x) % k) + k) % k; res += cnt[sum]++; } return res;}