Count the number of subarrays whose sum is divisible by k

Medium

📘 Problem Statement

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

🔍 Example

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]

🛠️ Solution

❌ Brute Force Approach (Inefficient)

  • Try all possible subarrays and count how many of them have sum divisible by k
def numberOfSubarrays(nums, k):
    count = 0
    n = len(nums)

    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total % k == 0:
                count += 1
    return count

The total complexity of this solution is O(n2)O(n^2). Not efficient for large arrays.

⚡ Optimized Approach: Prefix Sum

💡 Key Idea:

We know:

If prefix_sum[j] % k == prefix_sum[i - 1] % k, then the subarray [i..j] is divisible by k.

📘 Why This Works ?

  • sum(i..j) = prefix_sum[j] - prefix_sum[i - 1]

  • so ,

    (prefix_sum[j] - prefix_sum[i - 1]) % k == 0
→ prefix_sum[j] % k == prefix_sum[i - 1] % k

✅ Strategy:

  • Track prefix_sum % k at each index.
  • Use a hashmap to count how many times each mod value has appeared.
  • For current prefix_sum mod, add count_map[mod] to the result.
  • Initialize count_map = {0: 1} to handle subarrays starting from index 0.
def subarraysDivByK(nums, k):
    subarray_count = 0
    num_so_far = 0
    freq_count = {0 : 1} # For subarrays starting at index 0
    for num in nums:
        num_so_far += num # prefix sum
        remainder = num_so_far % k
    
        subarray_count += freq_count.get(remainder, 0)
        freq_count[remainder] = freq_count.get(remainder, 0) + 1
        
    return subarray_count

⏱️ Time & Space Complexity

Operation Complexity
Time O(n)O(n)
Space O(k)O(k)