#974

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Subarray Sums Divisible by K

Count the number of subarrays whose sum is divisible by a given integer k using array scanning and hash lookup.

Problem Statement

Given an integer array nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k. A subarray is a contiguous part of the array, and for each subarray, we need to determine if its sum modulo k equals zero.

To solve this, we utilize array scanning combined with a hash table to track cumulative sums modulo k. For each element, we compute the running sum and store the number of times that sum modulo k has occurred, which allows us to efficiently count the qualifying subarrays.

Examples

Example 1

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

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]

Example 2

Input: nums = [5], k = 9

Output: 0

Example details omitted.

Constraints

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
2 <= k <= 104

Solution Approach

Use Prefix Sum and Modulo Operation

Track the cumulative sum of elements as we iterate through the array. For each sum, take its modulo k. If a sum modulo k has occurred previously, that means there exists a subarray with a sum divisible by k. Use a hash map to store the frequency of each modulo result.

Hash Map to Track Modulo Frequencies

As you traverse the array, keep updating the hash map with the frequency of each modulo value. When encountering the same modulo value again, the difference between these sums forms subarrays whose sum is divisible by k.

Edge Case Handling

Ensure to handle edge cases like very small arrays or when the sum of elements is directly divisible by k. Initialize the hash map with a base case to account for subarrays starting from the beginning of the array.

Complexity Analysis

Metric	Value
Time	O(n + k)
Space	O(k)

The time complexity is O(n + k), where n is the length of the array and k is the divisor. The space complexity is O(k), due to the hash map storing the modulo results. The algorithm efficiently handles the constraints by reducing the need for nested loops, relying instead on prefix sums and hash lookups.

What Interviewers Usually Probe

The candidate demonstrates an understanding of prefix sums and how they relate to solving modular arithmetic problems in subarrays.
The candidate effectively applies hash maps for optimized lookups, showcasing an ability to avoid brute force solutions.
The candidate handles edge cases, ensuring their solution works even for small arrays and corner scenarios.

Common Pitfalls or Variants

Common pitfalls

Failing to account for negative numbers when calculating modulo values, which can lead to incorrect results.
Overcomplicating the problem by attempting nested loops or brute force approaches when hash maps can provide a more efficient solution.
Not handling the case where the sum of the subarray itself is divisible by k, especially for the first element of the array.

Follow-up variants

Given an array and a divisor, count the number of subarrays whose sum is divisible by a different integer or set of integers.
Modify the problem to find the longest subarray whose sum is divisible by k.
Instead of divisibility, solve for subarrays whose sum is a multiple of k or meets other modular constraints.

FAQ

What is the core pattern behind Subarray Sums Divisible by K?

The core pattern is using array scanning along with a hash map to track prefix sums modulo k, allowing efficient subarray sum checks.

How do I handle negative numbers in the Subarray Sums Divisible by K problem?

Ensure that the modulo operation handles negative values correctly by adjusting the result to always be non-negative, typically by adding k before taking modulo.

What is the time complexity of the Subarray Sums Divisible by K solution?

The time complexity is O(n + k), where n is the array length and k is the divisor, because we scan the array once and perform constant time hash map lookups.

How do hash maps improve the performance of the Subarray Sums Divisible by K problem?

Hash maps allow for constant-time lookups of previously seen modulo results, reducing the time complexity from O(n^2) to O(n) for the problem.

Can you provide an example of solving Subarray Sums Divisible by K?

Given nums = [4,5,0,-2,-3,1] and k = 5, there are 7 subarrays whose sum is divisible by 5: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].

terminal

Solution

Solution 1: Hash Table + Prefix Sum

Suppose there exists $i \leq j$ such that the sum of $\textit{nums}[i,..j]$ is divisible by $k$. If we let $s_i$ represent the sum of $\textit{nums}[0,..i]$ and $s_j$ represent the sum of $\textit{nums}[0,..j]$, then $s_j - s_i$ is divisible by $k$, i.e., $(s_j - s_i) \bmod k = 0$, which means $s_j \bmod k = s_i \bmod k$. Therefore, we can use a hash table to count the number of prefix sums modulo $k$, allowing us to quickly determine if there exists a subarray that meets the condition.

1

2

3

4

5

6

7

8

9

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = s = 0
        for x in nums:
            s = (s + x) % k
            ans += cnt[s]
            cnt[s] += 1
        return ans

Continue Practicing

#930 binary subarrays with sum #1074 number of submatrices that sum to target #1124 longest well performing interval