Subarray Sums Divisible by K Medium 0 attempts
LeetCode ↗

Subarray Sums Divisible by K

Medium ArrayTwo Pointers LeetCode

Given an integer array nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: The 7 subarrays are: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3]

Example 2:

Input: nums = [5], k = 9
Output: 0

Edge cases: Array with zeros (sum 0 is divisible by any k). Negative numbers — remainder handling differs by language.

Sample Input
nums = [4,5,0,-2,-3,1], k = 5
Sample Output
7
Constraints
  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4
Test Cases
Case 1
Args: [[4,5,0,-2,-3,1],5] Expected: 7
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.

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