[Leetcode] 974. Subarray Sums Divisible by K

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

initial

i just dont know but theres some maths. Let say we have a prefix sum of sum(right) and sum(left).

sum(right)-sum(left-1) is the sum of our subarray and
(sum(right)-sum(left-1)) % k should be 0 for the subarray to be valid.
(sum(right)-sum(left-1)) % k =0
sum(right) %k = sum(left-1) % k
r1 = r2

So the remainder is the same for num[left:right+1] sum, where if we found a remainder that we have seen before, the occurrence freq shows how many valid left pointer we can form a valid subarry that ends on the right pointer.

also we have to add k to the current sum that is % by k to always have a remainder range from 0 to k-1. (tbc im not sure why)

if remainder is 0, by itself it is already a valid subaray so we initalise our dicitonary to have a vlaue of 1 for remainder 0

sol

from collections import Counter
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        length=len(nums)
        counter=Counter({0:1})
        sum=0
        ans=0
        for num in nums:
            sum = (sum+num+k)%k
            ans += counter[sum]
            counter[sum]+=1
        return ans

complexity

n time
k space