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

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[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

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4

Thinking Process

  1. Modulo Property: If two prefix sums have the same modulo value, the subarray between them is divisible by k
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, cnt = 0;
        vector<int> prefixMods(k, 0);
        prefixMods[0] = 1; 
        for(int num: nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            cnt += prefixMods[prefixMod];
            prefixMods[prefixMod]++;
        }
        return cnt;
    }
};

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Modulo Property: If two prefix sums have the same modulo value, the subarray between them is divisible by k

How the code works:

  1. Modulo Property: If two prefix sums have the same modulo value, the subarray between them is divisible by k
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input nums = [4,5,0,-2,-3,1], k = 5, expected output 7:

There are 7 subarrays with a sum divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(k) - Array of size k to store modulo counts (more efficient than O(n) hash map)
Problem Goal Technique Space Complexity
LC 560 Count subarrays with sum = k Prefix Sum + Hash Map O(n)
LC 325 Maximum length subarray with sum = k Prefix Sum + Hash Map O(n)
LC 974 Count subarrays divisible by k Prefix Modulo + Array O(k)

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Modulo Property: If two prefix sums have the same modulo value, the subarray between them is divisible by k
  2. Negative Modulo Handling: Use (num % k + k) % k to ensure non-negative modulo for negative numbers
  3. Array vs Hash Map: Since modulo values are in range [0, k-1], we can use an array instead of a hash map, saving space
  4. Initial State: Initialize with prefixMods[0] = 1 to handle subarrays starting from index 0
  5. Integer Overflow Prevention: The modulo operation naturally prevents integer overflow by keeping values in range [0, k-1]

References

Template Reference