{x}
blog image

Subarray Sums Divisible by K

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 part of an array.

 

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 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

Solution Explanation: Subarray Sums Divisible by K

This problem asks to find the number of non-empty subarrays whose sum is divisible by a given integer k. The most efficient solution uses a combination of prefix sums and a hash table (or dictionary).

Core Idea:

The key insight is that if the sum of a subarray nums[i:j] (inclusive) is divisible by k, then (prefix_sum[j] - prefix_sum[i-1]) % k == 0. This implies that prefix_sum[j] % k == prefix_sum[i-1] % k. Therefore, we only need to track the remainders of prefix sums when divided by k.

Algorithm:

  1. Initialization:

    • Create a hash table (dictionary in Python) cnt to store the frequency of each remainder of the prefix sum. Initialize cnt[0] = 1 because an empty subarray (which has a sum of 0) is implicitly divisible by k.
    • Initialize ans = 0 to store the count of subarrays with sums divisible by k.
    • Initialize s = 0 to represent the current prefix sum.

  2. Iteration:

    • Iterate through the input array nums.
    • For each element x:
      • Update the prefix sum: s = (s + x) % k. We use the modulo operator (%) to keep track of only the remainder. We also handle negative remainders by adding k and taking the modulo again, ensuring non-negative remainders.
      • Update the count of subarrays: ans += cnt[s]. This adds to ans the number of times the current remainder s has appeared as a prefix sum remainder before. This means we've found a subarray ending at the current position whose sum is divisible by k.
      • Update the frequency count: cnt[s] += 1. Increment the count of the current remainder in the hash table.

  3. Return:

    • After iterating through the entire array, return ans.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Hash table lookups and insertions are considered O(1) on average.

Space Complexity: O(k), in the worst case, the hash table might store remainders from 0 to k-1. In practice, it's often much less than k.

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript all implement this algorithm. They differ slightly in syntax and handling of hash table operations, but the core logic remains the same. The key aspects to note are:

  • Handling negative remainders: The expression ((s + x) % k + k) % k ensures that the remainder is always non-negative.
  • Efficient hash table usage: The code leverages built-in hash table or dictionary functionalities for efficient lookups and updates.

This approach is significantly more efficient than brute-force methods (which would have O(n^2) time complexity) because it cleverly uses the properties of prefix sums and modular arithmetic to reduce the time complexity to linear.