Subarray Sums Divisible by K

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}