Subarray Sums Divisible by K Medium 0 attempts
LeetCode ↗

Subarray Sums Divisible by K

Medium ArrayTwo Pointers LeetCode

You're given an integer array nums and an integer k. Count how many contiguous, non-empty subarrays have a sum that's evenly divisible by k.

Edge cases: A subarray summing to zero counts, since zero is divisible by any k. Watch out for negative numbers — how the remainder is computed can differ across languages.

Input Format
Implement subarraysDivByK(nums, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [4,5,0,-2,-3,1]
k = 5
Output
7

Example 2

Input
nums = [-1,2,9]
k = 2
Output
2
Constraints
  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4
Test Cases (2)
Case 1
Args: [[4,5,0,-2,-3,1],5] Expected: 7
Case 2
Args: [[-1,2,9],2] Expected: 2
Topics
ArrayTwo Pointers

Approach: Prefix Sum Remainders

If two prefix sums have the same remainder when divided by k, the subarray between them sums to a multiple of k. Count remainder frequencies as you go. Be careful with negative remainders — add k and mod again to normalize.

javascript
function subarraysDivByK(nums, k) {
  const count = new Array(k).fill(0);
  count[0] = 1;
  let prefixSum = 0;
  let result = 0;

  for (const num of nums) {
    prefixSum += num;
    let rem = ((prefixSum % k) + k) % k;
    result += count[rem];
    count[rem]++;
  }
  return result;
}

Time Complexity: O(n)

Space Complexity: O(k)

Saved in this browser only. Private to you.

JavaScript