Subarray Sum Divisible by K - Two Pointers / Prefix Sum

Problems
1

https://algo.monster/problems/subarray_sum_divisible

2

def subarray_sum_divisible(nums, k):
left, right = 0, 0
count = 0
n = len(nums)

while left < n:
    while right < n:
        total_sum = sum(nums[left:right+1])
        if total_sum % k == 0:
            count += 1
        right += 1
    right = left + 1
    left = right
return count
3

For those who are still getting confused, I think I have an easier version here:
This is about mod arithmetics. The question want a program to count the number of subarrays nums[idx:jdx] that is divisible by the given number k, that is: sum_(i = idx to jdx) n_i % k = 0.
From subarray sum, we know that sum_(i = idx to jdx) n_i = sum_(i = 0 to jdx) n_i - sum(i = 0 to idx) n_i, combining the equations we have:
[sum_(i = 0 to jdx) n_i - sum(i = 0 to idx) n_i] % k = 0

There is a formula for modulo addition/subtraction:
(a + b)%c = (a%c + b%c)%c
(a - b)%c = (a%c - b%c)%c

Applying this we have:
[[sum_(i = 0 to jdx) n_i] % k - [sum(i = 0 to idx) n_i] % k] % k = 0

Now, notice 0 % k = 0, then we have [[sum_(i = 0 to jdx) n_i] % k - [sum(i = 0 to idx) n_i] % k] % k = 0 % k = 0, that means we can argue that:
[sum_(i = 0 to jdx) n_i] % k - [sum(i = 0 to idx) n_i] % k = 0

which gives:
[sum_(i = 0 to jdx) n_i] % k = [sum(i = 0 to idx) n_i] % k

This suggest that if we can find a value prefix sum % k that is equal to the current prefix sum % k that we are iterating on, then we found a subarray nums[idx:jdx] that is divisible by k.

To further elaborate, if we use a hashmap to store the index idx as value with the key (prefix sum % k), when we find a location jdx such that (current prefix sum % k == prefix sum % k), then the sub array between idx and jdx is what we are looking for. If we count these occurence, we will be able to get the totoal count of subarray that is divisible by k.

With this, we can use a hashmap to store the number of occurence for each remainder (prefix sum % k) on the fly and add to a grand total as appropiate.

Code:
def subarray_sum_divisible(nums: List[int], k: int) → int:
n = len(nums)
count = 0
if n == 0:
return count

prefixRemainderCount = defaultdict(int)
prefixRemainderCount[0] = 1 # 1 way to count prefix sum % k == 0 when there is only one entry and the number is multiple of k
currSum = 0
for idx in range(n):
    currSum += nums[idx]
    if currSum % k in prefixRemainderCount:
        count += prefixRemainderCount[currSum % k]
    prefixRemainderCount[currSum % k] += 1
return count
4

This is the brute force solution. You’re generating all subarrays and summing them up which is O(n^3) time.

5

The overall attempt with AlgoMonster is pretty beautiful and cool, but I think it’s not acceptable to pay for the content and only have 1 test case to test our algorithm…

6

This 1 line explanation is un acceptable, esp. since we’re paying for premium content. I had to dig through LC solutions, that are explained far better than the official soln. here.

7

I subscribe to the other comments saying this explanation is…let’s say unsubstantial.

Here is one that offers a lot of insight in the process of choosing the solution presented (modulo computations): https://www.youtube.com/watch?v=u9m-hnlcydk

8

BTW, in python, you don’t need this complement = (k - remainder) % k sice % (modulo) always returns range [0, 5) (positive remainder)

9

I paid 90$ for this kind of explanation. What a joke.