'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List


class Solution:
    # O(n) for S and T, n as len(A)
    def subarraysDivByK1(self, A: List[int], K: int) -> int:
        ct = 0
        prefix = 0
        # pay attention to the corner case, can have empty list for prefixSum as 0
        h = {0:1} # k: prefix sum % K, v: appearance of such case
        for val in A:
            prefixSum = (prefixSum + val) % K
            # first time seeing prefix doesn't mean anything
            # second time seeing it means we have subarray we want
            ct += h.get(prefixSum, 0) 
            h[prefixSum] = h.get(prefixSum, 0) + 1
        return ct


    # O(N) for S and T, N as len(A)
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        prefixSum = 0
        count = [1] + [0] * K
        for a in A:
            prefixSum = (prefixSum + a) % K
            res += count[prefix]
            count[prefix] += 1
        return res
    
    
    