[974] Subarray Sums Divisible by K

Link: https://leetcode.com/problems/subarray-sums-divisible-by-k/description/

1. Thinking Process

Logic: Using Prefix Sum && Remainder

We need to find the number of continuous subarrays divisible by k. The solution relies on the properties of Prefix Sums and Modular Arithmetic.

Core Concept

The sum of a subarray from index $i$ to $j$ can be expressed as:

$$Sum(i, j) = Prefix[j] - Prefix[i-1]$$

For this subarray sum to be divisible by $k$, the following condition must be met:

$$(Prefix[j] - Prefix[i-1]) \pmod k = 0$$

This equation can be rearranged to:

$$Prefix[j] \pmod k = Prefix[i-1] \pmod k$$

Key Insight: If two prefix sums have the same remainder when divided by $k$, the subarray formed between them is divisible by $k$.

Complexity: $O(N)$

2. Solution

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        ans=0
        pre_sum=0
        rest_list=[0]*k

        for number in nums:
            pre_sum = (pre_sum + number) % k
            if pre_sum == 0:
                ans+=1
            rest_list[pre_sum]+=1

        for rest in rest_list:
            if rest > 1:
                ans += (rest * (rest -1)) // 2
        return ans

3. Retrospective

Python HashMap

Why hmap = {0: 1}?

This initialization handles the Base Case.

• We need to count subarrays that start from the very beginning (index 0).
• Conceptually, the prefix sum before the array starts is 0, which has a remainder of 0.
• By initializing {0: 1}, we ensure that if a PrefixSum at index $i$ has a remainder of 0, it can pair with this initial value to form a valid subarray.

Why use the formula $\frac{n(n-1)}{2}$?

This comes from Combinatorics.

• If we find $n$ prefix sums that share the same remainder, any pair of them (a start point and an end point) forms a valid subarray.
• We need to choose 2 points out of n candidates. This is calculated using the combination formula $_nC_2$:

$$\binom{n}{2} = \frac{n (n-1)}{2}$$

4. References