leetcode-hashmap

974. Subarray Sums Divisible by K.py

class Solution:
    """
    
    Thought Process: 
        1.prefix sum+get all pair i, j -> O(n^2)
    [4,5,0,-2,-3,1]
            i
     j j j  j
     
     
     [1,2,3]
     [0,1,3,6]
      
        i
      j 
          i
      j j   
             i
      j j  j
        2.Prefix sum + Hashmap
        Prerequisite:
            1. That is the proof why sum(0, i) % k = sum(0,j) % k if sum(i, j) is divisible by K
            2. Consider sum(i, j) % k == 0 and i == 0. That's why we need count[0] = 1

   Note:
        1. Module: 同餘數
                比如說：

                4 除以 3 餘 1
                10 除以 3 餘 1
                我們就可以會說 4≡10 (mod 3) ，意思是「4和10在除以3的情況下是「同餘的」」

                其他例子：

                5 除以 2 餘 1
                7 除以 2 餘 1

                因此 5≡7 (mod 2)
    Ref:
        https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/310767/(Python)-Concise-Explanation-and-Proof
    """
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        prefix_sum = [0]*(n+1)
        cum_sum = 0
        for i, a in enumerate(A):
            cum_sum+=a
            prefix_sum[i] = cum_sum
        ans = 0
        for i in range(1, n+1):
            for j in range(i):
                cum_sum = prefix_sum[i]-prefix_sum[j]
                if cum_sum % K == 0:
                    ans += 1
        return ans
                
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        cum_sum = 0
        count = collections.defaultdict(int)
        # handle this case sum(i, j) % k == 0 and i == 0, where j > i.
        count[0] = 1
        ans = 0
        for a in A:
            cum_sum+=a
            ans += count[cum_sum%K]
            count[cum_sum%K]+=1
        return ans
    
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        """
        more readable version
        T:O(n)
        S:O(n)
        """
        n = len(A)
        # handle this case sum(i, j) % k == 0 and i == 0, where j > i.
        count = {0:1}
        ans = 0
        cum_sum = 0
        for a in A:
            cum_sum+=a
            key = cum_sum%K
            if key in count:
                ans += count[key]
                count[key] +=1
            else:
                count[key] = 1
        return ans