Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.
 

Example 1:
Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

 
Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

Difficulty: interview

Starter code:

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        

Solutions:
# Calculate the prefix sum and count it.
# In c++ and java, a % K + K takes care of the cases where a < 0.
# Python

class Solution: 
    def subarraysDivByK(self, A, K):
        res = 0
        prefix = 0
        count = [1] + [0] * K
        for a in A:
            prefix = (prefix + a) % K
            res += count[prefix]
            count[prefix] += 1
        return res
    
# If a subarray is divisible by K, it has to be a multiple of K

# a-b=n*k, a = running total, b = any previous subarray sum, same as original prefix sum problems.

# We want to solve for b, so using basic algebra, b=a-n*k

# We don't know what n is, so we can get rid of n by modding every element by k
# (b%k) = (a%k) - (n*k)%k

# since n*k is a multiple of k and k goes into it evenly, the result of the (n *k)%k will be 0

# therefore
# b%k = a%k

# is the same as the formula we defined earlier, a-b=n*k

# where b = running total, a = any previous subarray sum

# So we just have to see if running total mod k is equal to any previous running total mod k


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        count = [1] + [0] * K
        prefix = 0
        for a in A:
            prefix = (prefix + a) % (K)
            res += count[prefix]
            count[prefix] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        B = [a % K for a in A]
        
        sum_dict = {}
        ans = 0
        curr_sum = 0
        sum_dict[0] = 1
        
        n = len(B)
        
        for i, num in enumerate(B):
            curr_sum = (curr_sum + num) % K
            if curr_sum in sum_dict:
                ans += sum_dict[curr_sum]
                
            sum_dict[curr_sum] = sum_dict.get(curr_sum, 0) + 1
         
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        countPrefs = {0: 1}
        total = 0
        res = 0
        for i, num in enumerate(A):
            total += num
            res += countPrefs.get(total % K , 0)
            if total % K in countPrefs:
                countPrefs[total % K] += 1
            else:
                countPrefs[total % K] = 1
        return res


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res, n, cache, sv = 0, len(A), collections.defaultdict(int), 0
        cache[0] = 1
        for i, v in enumerate(A):
            sv += v
            if cache[sv % K] > 0:
                res += cache[sv % K]
            cache[sv % K] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        pre = 0
        res = 0
        d = {0: 1}
        for a in A:
            pre = (pre + a) % K
            res += d.get(pre, 0)
            d[pre] = d.get(pre, 0) + 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        cumsum = [0]
        for n in A:
            cumsum.append(cumsum[-1]+n)
        print((cumsum, A))
        cnt = 0
        # for i in range(len(A)):
        #     for j in range(i+1,len(A)):
        #         if (cumsum[j]-cumsum[i])%K == 0:
        #             cnt += 1
        # return cnt
        count = [0]*K
        for x in cumsum:
            count[(x%K+K)%K] += 1
            
        cnt = 0
        for num in count:
            cnt += num*(num-1)//2
        return cnt


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        mod_count = Counter({0:1})
        
        ans = 0
        for s in [*accumulate(A)]:
            m = s % K
            if m in mod_count:
                ans += mod_count[m]
            mod_count[m] += 1
        return ans

# Refer to Problem 523 for more info 
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        currsum = 0
        d = Counter()
        d[0] = 1
        for i, num in enumerate(A):
            currsum+= num
            currsum %= K
            if currsum in d:
                #all the past subarray end points where the remainder is same as the current one will act as starting point for the current subarray so that the total sum is divisible by K 
                res+= d[currsum]
            d[currsum]+=1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        # (cs - cs[i]) % k == 0
        res = 0
        cs = 0
        seen = collections.Counter({0: 1})
        for i in range(len(A)):
            x = A[i]
            cs += x
            if cs % K in seen:
                res += seen[cs % K]
            seen[cs % K] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        m = defaultdict(int)
        m[0] = 1
        curr_sum = 0
        result = 0
        for a in A:
            curr_sum += a
            remainder = curr_sum % K
            if remainder in m:
                result += m[remainder]
            m[remainder] += 1
        return result

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        if not A:
            return 0
        # Instead of actual prefix sums, store prefix sums mod K
        # And don't have to store indices, just store count
        prefix_sums = defaultdict(int)
        prefix_sums[0] = 1
        cumsum = 0
        ans = 0
        for i, x in enumerate(A):
            cumsum = (cumsum + x) % K
            ans += prefix_sums[cumsum]
            prefix_sums[cumsum] += 1
        return ans

class Solution(object):
    def subarraysDivByK(self, A, K):
        nums = A
        k = K
        modDict = {}
        tempSumn = 0
        ans = 0
        continousSum = []
        
        for num in nums:
            tempSumn += num
            continousSum.append(tempSumn)
            remain = tempSumn%k
            
            if remain not in modDict:
                modDict[remain] = 0
            modDict[remain] += 1
        
        diff = k
        for i in range(0, len(continousSum)):
            if diff%k in modDict:
                ans += modDict[diff%k]
                
            diff = continousSum[i]
            modDict[diff%k] -= 1
        
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        sums = 0
        count = 0
        dic = {0:1}
        
        for a in A:
            sums = (sums + a) % K
            print(sums)
            if sums in dic:
                count += dic[sums]
                dic[sums] += 1
            else:
                dic[sums] = 1
                
        return count

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        su = 0 
        dic = {}
        count = 0
        for i in range(len(A)):
             
                su +=A[i]
                
                if(su%K==0):
                    count +=1
                if((su)%K in dic.keys()):
                  count += dic[(su)%K]
                
                
                if(su%K in dic.keys()):
                  dic[su%K] += 1
                else:
                  dic[su%K]  = 1
        print(dic)
        print(count)
        return count

'''
Contiguous sub array
Positive and negative
cannot be empty

return count


Create prefix

Loop through --> if remainder in prefix count += 1
add prefix % k into seen


4 9 9 7 4 5

4 4 4 5 4 0
'''
from collections import Counter
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        seen = Counter()
        
        prefix = [] # store sum up till and including this index
        curr_sum = 0
        for x in A:
            curr_sum += x
            prefix.append(curr_sum % K)
            
        ans = 0 
        for ix in range(len(A)):
            remainder = K - prefix[ix]
            if prefix[ix] in seen: # handle case whereby sub array = 0 or sub array = 5
                ans += seen[prefix[ix]]
            if prefix[ix] == 0:
                ans += 1
            seen[prefix[ix]] += 1
        return ans
            


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        A[0] = A[0]%K
        seen = {0:1}
        count = 0 
        for i in range(1,n):
            A[i] = (A[i] + A[i-1])%K
        for i in range(n):
            newTarget = (A[i] - K)%K
            if newTarget in seen: 
                count+= seen[newTarget]
            if A[i] in seen:
                seen[A[i]] += 1
            else:
                seen[A[i]] = 1
        return count 
            
            
            
        


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        cnt = Counter([0])
        pref, ans = 0, 0
        for a in A:
            pref = (pref + a) % K
            ans += cnt[pref]
            cnt[pref] += 1
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        prefix = [0]*len(A)
        prefix[0] = A[0]%K
        counter = Counter([prefix[0]])
        ans = 1 if prefix[0] == 0 else 0
        for i in range(1, len(A)):
            prefix[i] = (prefix[i-1] + A[i]) % K
            target = prefix[i] - 0
            ans += counter[target]
            if target == 0:
                ans += 1
            counter[prefix[i]] += 1
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        
        cumsum = 0
        complements = {0: 1}
        counts = 0
        for a in A:
            cumsum += a
            mods = cumsum % K
            counts += complements.get(mods, 0)
            complements[mods] = complements.get(mods, 0) + 1 
            
        return counts


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        '''
        Algorithm
        ---------
        We will keep track of the running sum s. We then take the
        modulo of the sum and record its frequency in a hash table.
        
        After the first pass the number of subarrays divisible by K
        is the sum of the frequencies of the remainders choose 2 -> c *(c - 1)//2
        '''
        
        # Hash table to store modulo
        ht = [0] * K
        
        sum = 0
        for num in A:
            sum += num
            ht[sum % K] += 1
        
        # handle the case of 0 remainder -> n * (n - 1) // 2 + n
        results = ht[0]
        
        for c in ht:
            results += (c * (c - 1)) // 2
        return results
        


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        prefix_sum = [0]
        for idx, i in enumerate(A):
            prefix_sum.append(i+prefix_sum[idx])
        print(prefix_sum)
        
        # now we go through and try to see if we've seen the pair number already
        
        num_enc = dict()
        total = 0
        for i in prefix_sum:
            if (i%K) in num_enc:
                total+=num_enc[i%K]
            if (i%K - K) in num_enc:
                total+=num_enc[i%K - K]
            if i%K not in num_enc:
                num_enc[i%K] = 0
            num_enc[i%K]+=1
        return total
            
            
                

        
#         total = 0
#         for i in range(0, len(A)):
#             curr_sum = A[i]
#             if curr_sum%K==0:
#                 total+=1
#             for j in range(i+1, len(A)):
#                 curr_sum+=A[j]
#                 if curr_sum%K==0:
#                     total+=1
#         return total
                
                
                
                
                
#         for wsize in range(1, len(A)):
#             i = 0
#             curr_sum = sum(A[j] for j in range(0, wsize+1))
#             while i + wsize < len(A):
                
#                 if i != 0:
#                     curr_sum-=A[i-1]
#                     curr_sum+=A[i+wsize]
#                 if curr_sum%5==0:
#                     total+=1
#                 print(i, i+wsize, wsize, curr_sum)
#                 i+=1
#         return total


class Solution:
    def TRIAlsubarraysDivByK(self, A: List[int], K: int) -> int:
        n = 0
        for i in range(len(A)):
            sum = 0
            for j in range(i,len(A)):
                sum+=A[j]
                if(sum%K==0):
                    n+=1
        return n
    
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        rems = [0]*len(A)
        for i in range(len(A)):
            if(i==0):
                rems[0] = A[0]%K
            else:
                rems[i] = (rems[i-1] + A[i])%K
        print(rems)
            
        count = list(Counter(rems).values())
        print(count)
        return(int(sum(n*(n-1)/2 for n in count)) + rems.count(0))


from collections import defaultdict

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        if not A:
            return 0
        # Instead of actual prefix sums, store prefix sums mod K
        prefix_sums = defaultdict(list)
        prefix_sums[0].append(-1)
        cumsum = 0
        ans = 0
        for i, x in enumerate(A):
            cumsum += x
            cumsum_mod = cumsum % K
            ans += len(prefix_sums[cumsum_mod])
            prefix_sums[cumsum_mod].append(i)
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        if not A or not K:
            return 0
        map = Counter()
        map[0] = 1
        sum = 0
        res = 0
        for num in A:
            sum += num
            sum %= K
            if sum < 0:
                sum += K
            if sum in map:
                res += map[sum]
            map[sum] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        prefix = [0] * (n+1)
        for i in range(1, n+1):
            prefix[i] = prefix[i-1] + A[i-1]
        for i in range(1, n+1):
            prefix[i] = prefix[i] % K
        d = defaultdict(list)
        ans = 0
        for i in range(1, n+1):
            if prefix[i] == 0:
                ans += 1
            if prefix[i] in d.keys():
                ans += len(d[prefix[i]])
            d[prefix[i]].append(i)
        return ans

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) ->int:
        count = [0]*K
        sum = 0
        for i in A:
            sum += i%K
            count[sum % K] += 1
        result = count[0]
        for j in count:
            result +=(j*(j-1))/2
        return int(result)

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        map = {}
        map[0] = 1
        sum, count = 0, 0
        
        for n in A:
            sum = (sum + n) % K
            
            if sum not in list(map.keys()):
                map[sum] = 1
            else:
                count += map[sum]
                map[sum] += 1
        
        return count


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        ans=0
        count=[1]+[0]*K
        prefix=0
        
        for num in A:
            prefix=(prefix+num)%K
            ans+=count[prefix]
            count[prefix]+=1
        
        return ans

import collections
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        counts = [0] * K
        
        total = 0
        
        for num in A:
            total += num
            counts[total % K] += 1
              
        
        result = counts[0]
        
        for count in counts:   
            result += (count*(count-1))//2
  

        return result

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        D, s = {0:1}, 0
        for a in A:
            s = (s + a) % K
            if s in D: 
                D[s] += 1
            else: 
                D[s] = 1
        return sum(i*(i-1)//2 for i in list(D.values()))


import collections
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        rem_array = [0]
        for num in A:
            rem_array.append((num+rem_array[-1])%K)
        
        counter = collections.Counter(rem_array)
        return sum(v*(v-1)//2 for v in counter.values())

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        count = 0
        mods = [0]
        modFreqs = defaultdict(lambda: 0)
        for num in nums:
            mod = (mods[-1] + num) % k
            if mod == 0:
                count += 1
            count += modFreqs[mod]
            mods.append(mod)
            modFreqs[mod] += 1
        return count

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        P = [0]
        for x in A:
            P.append((P[-1]  + x)%K)
        count = collections.Counter(P)
        return int(sum(v*(v-1)/2 for v in count.values()))

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        hash_map = collections.defaultdict(int)
        hash_map[0] = 1
        prefix = 0
        res = 0
        for i in range(len(A)):
            num = A[i]
            prefix = ( prefix + num ) % K
            res += hash_map[prefix]
            hash_map[prefix] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        P = [0]
        for x in A:
            P.append((P[-1] + x) % K)
            
        # print(P)

        count = collections.Counter(P)
        
        # print(count)
        return sum(v*(v-1)//2 for v in count.values())

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        arr, ans, curr = [1]+[0]*K, 0, 0
        for i in A:
            curr = (curr+i)%K
            ans += arr[curr]
            arr[curr] += 1
        return ans

from collections import defaultdict
from operator import add

def accum(op, l):
    if not l:
        return []
    v = l[0]
    ret = [v]
    for x in l[1:]:
        v = op(v, x)
        ret.append(v)
    return ret
    
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        B = accum(add, A)
        B = [0] + B
        B = [x % K for x in B]
        seen = defaultdict(lambda: 0)
        seen[0] = 1
        combinations = 0
        for s in B[1:]:
            target = s
            if seen[target] > 0:
                combinations += seen[target]
            seen[s] = seen[s] + 1
        return combinations

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        hashmap = [0] * K
        hashmap[0] = 1
        result = 0
        prefix = 0
        for i in range(len(A)):
            prefix = (prefix + A[i])%K
            hashmap[prefix] += 1
            result += (hashmap[prefix] - 1)

        return result


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        m = Counter()
        cur_sum = 0
        ans = 0
        for x in A:
            cur_sum += x
            ans += m[cur_sum % K]
            if cur_sum % K == 0:
                ans += 1
            print((x, m[cur_sum % K]))
            m[cur_sum % K] += 1
        return ans


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        #O(n^2) solutions: build all sub, find sum, divisible by K
        
        #O(n): store something with value % K
        
        '''
        #Running sum
        a - b = n * k, a is curr_sum, b is prev_sum
        We're looking for prev_sum that can add a to -> looking for b
        b = a - n * k 
        b % k = a % k
        -> see if running total % k -> find the prev_sum % k
        
        '''
        dp = [1] + [0] * K
        result = 0
        running_sum = 0
        for num in A:
            running_sum += num
            result += dp[running_sum % K]
            dp[running_sum % K] += 1
            
        return result

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        sums = 0
        d = {0:1}
        for num in A:
            sums = (sums + num) % K
            # if sums < 0:
            #     sums += K
            res += d.get(sums, 0)
            d[sums] = d.get(sums, 0) + 1
        return res
    
    # [4,9,9,7,4,5]
    # d = {
    #     0:1, 4:4, 2:1, 
    # }
    # res = 7
    # sums = 4
        


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        sum1=sum(A)
        count1=0
        dict1={0:1}
        rem1=0
        sum2=0
        for i in range(len(A)):
            sum2+=A[i]
            rem1=sum2%K
            if rem1<0:
                rem1+=k
                
                
            if rem1 in dict1:
                count1+=dict1[rem1]
                dict1[rem1]+=1
                
            else:
                dict1[rem1]=1
        print(dict1)
        return count1
                
            
                
            
            
            
            
            
            
                    


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        # use the prefix sum 
        prefix = [0]
        for a in A:
            prefix += [(prefix[-1] + a) % K]
        #count how many of them are the same
        cnt = collections.Counter(prefix)
        # for the index with the same remainder, randomly choose pairs
        return int(sum( v * (v-1) / 2 for v in list(cnt.values())))


from collections import defaultdict

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        seen = defaultdict(int, {0: 1})
        ret = psum = 0
        for n in A:
            psum = (psum + n) % K
            if psum in seen:
                ret += seen[psum]
            seen[psum] += 1
        return ret

from collections import Counter
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        presum = [0]
        for num in A:
            presum.append((presum[-1] + num) % K)    
            
        count = Counter(presum)
        return sum(c * (c - 1) // 2 for c in list(count.values()))
            
        


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        hm = {}
        hm[0] = 1
        prefix = 0
        count = 0
        for i in range(0, len(A)):
            prefix = (A[i] + prefix)%K
            if prefix in hm:
                count += hm[prefix]
            else:
                hm[prefix] = 0
            hm[prefix] += 1
        return count


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        prefix = 0
        count = [1] + [0] * K
        for a in A:
            prefix = (prefix + a) % K
            res += count[prefix]
            count[prefix] += 1
        return res

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        
        cumsum = 0
        counts = 0
        complements = {0: 1}
        for a in A:
            cumsum += a
            mods = cumsum % K
            counts += complements.get(mods, 0)
            complements[mods] = complements.get(mods, 0) + 1 
            
        return counts


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        prefixsum = 0
        remain = collections.defaultdict(int)
        remain[0] = 1
        
        res = 0
        for i in range(n):
            prefixsum += A[i]
            re = prefixsum % K
            res += remain[re]
            remain[re] += 1
        return res
            


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        
        res = 0
        lookup = {0:1}
        presum = 0
        for i, num in enumerate(A):
            presum += num
            remainder = presum % K
            res += lookup.get(remainder, 0)
            lookup[remainder] = lookup.get(remainder, 0) + 1
            
            
        return res


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        
        # P[i] stores sum up to index i
        P = [0]
        for x in A:
            P.append( (P[-1] + x) % K )
        
        count = collections.Counter(P)
        
        ans = 0
        for v in list(count.values()):
            ans += int(v*(v-1)*0.5)
        
        return ans
        #return sum( v*(v-1)//2 for v in count.values())
        
        


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        preSum = [0] 
        for num in A:
            preSum.append((preSum[-1]+num)%K)
        preSumCounter = Counter(preSum)
        return sum(v*(v-1)//2 for v in preSumCounter.values())

'''
https://leetcode.com/problems/continuous-subarray-sum/
'''
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        d = {0: 1}
        runningSum = 0
        sol = 0
        for i in range(len(A)):
            runningSum += A[i]
            newMod = runningSum % K
            if newMod not in d:
                d[newMod] = 0
            d[newMod] += 1
            sol += d[newMod] - 1
        return sol
            
            
                
                


'''
[4,5,0,-2,-3,1]

'''
class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        d = {0: 1}
        runningSum = 0
        sol = 0
        for i in range(len(A)):
            runningSum += A[i]
            newMod = runningSum % K
            if newMod not in d:
                d[newMod] = 0
            d[newMod] += 1
            sol += d[newMod] - 1
        return sol
            
            
                
                


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        
        
        prefixMod = 0
        hashTable = collections.defaultdict(int)
        total = 0
        curSum = 0
        hashTable[0] = 1
        
        for i,x in enumerate(A) :
           
            prefixMod = prefixMod + x
            
            prefixMod = prefixMod%K
           
            total += hashTable[prefixMod]
            
            hashTable[prefixMod] += 1
    
        return total