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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Range queries

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

Solutions:
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


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
		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


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:
				res += d[currsum]
			d[currsum] += 1
		return res


class Solution:

	def subarraysDivByK(self, A: List[int], K: int) -> int:
		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
		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


from collections import Counter

class Solution:

	def subarraysDivByK(self, A: List[int], K: int) -> int:
		seen = Counter()
		prefix = []
		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:
				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:
		ht = [0] * K
		sum = 0
		for num in A:
			sum += num
			ht[sum % K] += 1
		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)
		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


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)


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:
		(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:
		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
			res += d.get(sums, 0)
			d[sums] = d.get(sums, 0) + 1
		return res


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:
		prefix = [0]
		for a in A:
			prefix += [(prefix[-1] + a) % K]
		cnt = collections.Counter(prefix)
		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:
		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 = [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


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()))


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