You are given an array arr[] of size n. Find the total count of sub-arrays having their sum equal to 0.
Example 1:
Input:
n = 6
arr[] = {0,0,5,5,0,0}
Output: 6
Explanation: The 6 subarrays are 
[0], [0], [0], [0], [0,0], and [0,0].
Example 2:
Input:
n = 10
arr[] = {6,-1,-3,4,-2,2,4,6,-12,-7}
Output: 4
Explanation: The 4 subarrays are [-1 -3 4]
[-2 2], [2 4 6 -12], and [-1 -3 4 -2 2]
Your Task:
You don't need to read input or print anything. Complete the function findSubarray() that takes the array arr and its size n as input parameters and returns the total number of sub-arrays with 0 sum. 
 
Expected Time Complexity: O(n*log(n))
Expected Auxilliary Space: O(n)
 
Constraints:    
1 <= n <= 10^6
-10^9 <= arr[ i ] <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to count subarrays with sum equal to 0.

    def findSubArrays(self,arr,n):

        

        #return: count of sub-arrays having their sum equal to 0

Solutions:
class Solution:

	def findSubArrays(self, arr, n):
		dict = {}
		count = 0
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum == 0:
				count += 1
			if sum in dict:
				count += dict[sum]
				dict[sum] += 1
			else:
				dict[sum] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		prefix_sum_freq = {}
		count = 0
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum == 0:
				count += 1
			if curr_sum in prefix_sum_freq:
				count += prefix_sum_freq[curr_sum]
			prefix_sum_freq[curr_sum] = prefix_sum_freq.get(curr_sum, 0) + 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		prefix = 0
		d = {}
		count = 0
		for i in range(n):
			prefix += arr[i]
			if prefix not in d:
				d[prefix] = 0
			d[prefix] += 1
			if prefix == 0:
				count += 1
		for key in d:
			count += d[key] * (d[key] - 1) // 2
		return count


class Solution:

	def solve(self, arr, n):
		cnt = 0
		for i in range(n):
			for j in range(i, n):
				if sum(arr[i:j + 1]) == 0:
					cnt += 1
		return cnt

	def findSubArrays(self, arr, n):
		sum_map = {0: 1}
		summ = 0
		cnt = 0
		for i in range(n):
			summ += arr[i]
			if sum_map.get(summ):
				cnt += sum_map[summ]
				sum_map[summ] += 1
			else:
				sum_map[summ] = 1
		return cnt


class Solution:

	def findSubArrays(self, arr, n):
		mp = dict({0: 1})
		total = 0
		res = 0
		for item in arr:
			total += item
			if total in mp:
				res += mp[total]
			if total not in mp:
				mp[total] = 0
			mp[total] += 1
		return res


class Solution:

	def findSubArrays(self, arr, n):
		prefixSumFreq = {}
		prefixSum = 0
		count = 0
		for num in arr:
			prefixSum += num
			if prefixSum == 0:
				count += 1
			if prefixSum in prefixSumFreq:
				count += prefixSumFreq[prefixSum]
			if prefixSum in prefixSumFreq:
				prefixSumFreq[prefixSum] += 1
			else:
				prefixSumFreq[prefixSum] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		c = 0
		currsum = 0
		s = 0
		d = {}
		for i in arr:
			s = s + i
			d[s] = 0
		for i in arr:
			currsum = currsum + i
			if currsum == 0:
				c = c + 1
			if currsum in d:
				c = c + d[currsum]
			d[currsum] += 1
		return c


class Solution:

	def findSubArrays(self, arr, n):
		dict = {}
		dict[0] = 1
		ans = 0
		sum_ele = 0
		for i in arr:
			sum_ele += i
			if sum_ele in dict:
				ans += dict[sum_ele]
				dict[sum_ele] += 1
			else:
				dict[sum_ele] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		g = {}
		g[0] = 1
		sum = 0
		count = 0
		for i in range(n):
			sum = sum + arr[i]
			x = sum
			if x not in g:
				g[x] = 1
			else:
				g[x] += 1
				count += g[x] - 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		hash = {0: 1}
		ans = 0
		curr = 0
		for ele in arr:
			curr += ele
			if curr in hash:
				ans += hash[curr]
				hash[curr] += 1
			else:
				hash[curr] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		ans = 0
		k = {}
		sum = 0
		for i in arr:
			sum += i
			if sum == 0:
				ans += 1
			if sum in k:
				ans += k[sum]
				k[sum] += 1
			else:
				k[sum] = 1
		return ans


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		prefix = [arr[0]]
		for i in range(1, n):
			prefix.append(prefix[-1] + arr[i])
		mpFreq = defaultdict(int)
		for i in range(n):
			mpFreq[prefix[i]] += 1
		result = 0
		for i in mpFreq:
			k = mpFreq[i]
			result += int(k * (k - 1) / 2)
		result += mpFreq[0]
		return result


from collections import defaultdict

class Solution:

	def findSubArrays(self, A, n):
		ans = csum = 0
		D = defaultdict(int)
		D[0] = 1
		for i in A:
			csum += i
			ans += D[csum]
			D[csum] += 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		x = 0
		ans = 0
		i = 0
		while i < n and arr[i] == 0:
			ans += 1
			i += 1
		for i in range(n):
			x += arr[i]
			arr[i] = x
		if arr[0] != 0:
			dic = {0: 1}
		else:
			dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		for i in dic.keys():
			ans += dic[i] * (dic[i] - 1) // 2
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		d = {0: 1}
		sum_val = 0
		ans = 0
		for i in arr:
			sum_val += i
			if sum_val in d:
				ans += d[sum_val]
				d[sum_val] += 1
			else:
				d[sum_val] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		c = 0
		hashmap = {}
		out = []
		sum1 = 0
		for i in range(n):
			sum1 += arr[i]
			if sum1 == 0:
				out.append((0, i))
				c += 1
			al = []
			if sum1 in hashmap:
				al = hashmap.get(sum1)
				for it in range(len(al)):
					out.append((al[it] + 1, i))
					c += 1
			al.append(i)
			hashmap[sum1] = al
		return c


class Solution:

	def findSubArrays(self, arr, n):
		subarray_count = {}
		cumulative_sum = 0
		count = 0
		for i in range(n):
			cumulative_sum += arr[i]
			if cumulative_sum == 0:
				count += 1
			if cumulative_sum in subarray_count:
				count += subarray_count[cumulative_sum]
			if cumulative_sum in subarray_count:
				subarray_count[cumulative_sum] += 1
			else:
				subarray_count[cumulative_sum] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		d = {0: 1}
		s = 0
		res = 0
		for num in arr:
			s += num
			if s in d:
				res += d[s]
			d[s] = d.get(s, 0) + 1
		return res


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		freq = {0: 1}
		count = 0
		summ = 0
		for i in arr:
			summ += i
			if summ in freq:
				count += freq[summ]
				freq[summ] += 1
			else:
				freq[summ] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		p_sum = []
		sum = 0
		ans = 0
		for i in range(n):
			sum += arr[i]
			p_sum.append(sum)
			if sum == 0:
				ans += 1
		my_dict = dict()
		for i in range(n):
			if p_sum[i] in my_dict:
				ans += my_dict[p_sum[i]]
				my_dict[p_sum[i]] = my_dict[p_sum[i]] + 1
			else:
				my_dict[p_sum[i]] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		a = 0
		j = 0
		d = {0: 1}
		for i in range(n):
			a += arr[i]
			if a not in d:
				d[a] = 1
			else:
				j += d[a]
				d[a] += 1
		return j


class Solution:

	def findSubArrays(self, arr, n):
		hm = {}
		ans = 0
		suma = 0
		for x in range(n):
			suma += arr[x]
			if suma == 0:
				ans += 1
			if suma not in hm:
				hm[suma] = 1
			else:
				ans += hm[suma]
				hm[suma] += 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		prefix_sum = {}
		count = 0
		sum_so_far = 0
		for i in range(n):
			sum_so_far += arr[i]
			if sum_so_far == 0:
				count += 1
			if sum_so_far in prefix_sum:
				count += prefix_sum[sum_so_far]
				prefix_sum[sum_so_far] += 1
			else:
				prefix_sum[sum_so_far] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		d = {}
		d1 = {}
		c = 0
		s = 0
		s1 = 0
		mm = 0
		for i in range(len(arr)):
			s = s + arr[i]
			if s not in d:
				d[s] = 1
			else:
				d[s] = d[s] + 1
		for i in d:
			if i == 0:
				c = c + d[i] * (d[i] + 1) // 2
			else:
				c = c + d[i] * (d[i] - 1) // 2
		return c


class Solution:

	def findSubArrays(self, arr, n):
		presum = 0
		count = 0
		hmap = {}
		ans = 0
		for i in range(n):
			presum += arr[i]
			if presum == 0:
				ans += 1
			hmap[presum] = hmap.get(presum, 0) + 1
		for (key, val) in hmap.items():
			ans += val * (val - 1) // 2
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		count = 0
		map1 = {}
		map1[0] = 1
		sum1 = 0
		for num in arr:
			sum1 += num
			if sum1 in map1:
				count += map1[sum1]
				map1[sum1] += 1
			else:
				map1[sum1] = 1
		return count


from collections import *

class Solution:

	def findSubArrays(self, arr, n):
		n = len(arr)
		sum_map = defaultdict(int)
		sum_map[0] = 1
		cur_sum = 0
		count = 0
		for i in range(n):
			cur_sum += arr[i]
			count += sum_map[cur_sum]
			sum_map[cur_sum] += 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		hm = {0: 1}
		s = 0
		c = 0
		for i in range(len(arr)):
			s = s + arr[i]
			if s in hm:
				c = c + hm[s]
				hm[s] = hm[s] + 1
			else:
				hm[s] = 1
		return c


import math

class Solution:

	def findSubArrays(self, arr, n):
		count = 0
		sum_dict = {}
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum == 0:
				count += 1
			if sum in sum_dict:
				count += sum_dict[sum]
			if sum in sum_dict:
				sum_dict[sum] += 1
			else:
				sum_dict[sum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		d = defaultdict(list)
		d[0] = [-1]
		summ = 0
		count = 0
		for i in range(len(arr)):
			summ += arr[i]
			if summ not in d:
				d[summ] = [i]
			else:
				d[summ].append(i)
		for j in d.values():
			n = len(j)
			count += n * (n - 1) // 2
		return count


class Solution:

	def findSubArrays(self, arr, n):
		hash = {}
		ans = 0
		s = 0
		for el in arr:
			s += el
			if s == 0:
				ans += 1
			hash[s] = hash.get(s, 0) + 1
		for (k, cnt) in hash.items():
			ans += cnt * (cnt - 1) // 2
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		if n == 1:
			if arr[0] == 0:
				return 1
			else:
				return 0
		su = 0
		dic = {}
		dic[0] = 1
		count = 0
		for ele in arr:
			su += ele
			if su in dic:
				if dic[su] > 1:
					count += dic[su]
				else:
					count += 1
				dic[su] += 1
			else:
				dic[su] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		count = 0
		mp = {}
		prefix_sum = 0
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum == 0:
				count += 1
			if prefix_sum in mp:
				count += mp[prefix_sum]
			mp[prefix_sum] = mp.get(prefix_sum, 0) + 1
		return count


class Solution:

	def fact(self, n):
		if n == 0:
			return 1
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res

	def nCr(self, n, r=2):
		return self.fact(n) / (self.fact(r) * self.fact(n - r))

	def findSubArrays(self, arr, n):
		cur_sum = 0
		hm = {}
		res = 0
		for i in range(n):
			cur_sum += arr[i]
			if cur_sum == 0:
				res += 1
			if cur_sum in hm:
				hm[cur_sum] += 1
			else:
				hm[cur_sum] = 1
		for (i, j) in hm.items():
			if j > 1:
				res += self.nCr(j)
		return int(res)


from collections import Counter

class Solution:

	def findSubArrays(self, arr, n):
		ans = []
		d = {}
		sum_ = 0
		count = 0
		for i in range(n):
			sum_ += arr[i]
			ans.append(sum_)
		for i in range(n):
			if ans[i] == 0:
				count += 1
			if ans[i] not in d:
				d[ans[i]] = 1
			elif ans[i] in d:
				count += d[ans[i]]
				d[ans[i]] += 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		ans = []
		d = {}
		sum_ = 0
		count = 0
		for i in range(n):
			sum_ += arr[i]
			ans.append(sum_)
		for i in range(n):
			if ans[i] == 0:
				count += 1
			if ans[i] not in d:
				d[ans[i]] = 1
			elif ans[i] in d:
				count += d[ans[i]]
				d[ans[i]] += 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		hmap = {}
		su = 0
		ans = 0
		for i in range(n):
			su += arr[i]
			if su == 0:
				ans += 1
			if su in hmap:
				ans += hmap[su]
				hmap[su] += 1
			else:
				hmap[su] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		count = 0
		a = {}
		a[0] = 0
		s = 0
		ans = 0
		for i in range(n):
			s += arr[i]
			a[s] = a.get(s, -1) + 1
		for i in a.keys():
			ans += a[i] * (a[i] + 1) // 2
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		(count, s) = (0, 0)
		d = {}
		ps = []
		for i in range(n):
			s += arr[i]
			ps.append(s)
		for i in range(n):
			if ps[i] == 0:
				count += 1
			if ps[i] not in d:
				d[ps[i]] = 1
			else:
				count += d[ps[i]]
				d[ps[i]] += 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		p_s = 0
		c = 0
		f = {}
		for i in range(n):
			p_s += arr[i]
			if p_s == 0:
				c += 1
			if p_s in f:
				c += f[p_s]
				f[p_s] += 1
			else:
				f[p_s] = 1
		return c


class Solution:

	def findSubArrays(self, arr, n):
		res = []
		if len(arr) == 1:
			if arr[0] == 0:
				res.append([arr[0]])
				return len(res)
		prefix = {0: [-1]}
		running_sum = 0
		k = 0
		for (i, val) in enumerate(arr):
			running_sum += val
			diff = running_sum - k
			if diff in prefix:
				for val in prefix[diff]:
					res.append(arr[val + 1:i + 1])
			if running_sum in prefix:
				prefix[running_sum].append(i)
			else:
				prefix[running_sum] = [i]
		return len(res)


class Solution:

	def findSubArrays(self, arr, n):
		m = {0: 1}
		ans = 0
		cur = 0
		for el in arr:
			cur = cur + el
			if cur in m:
				ans = ans + m[cur]
				m[cur] += 1
			else:
				m[cur] = 1
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		count = 0
		s = 0
		h = {}
		for i in range(n):
			s += arr[i]
			if s == 0:
				count += 1
			if s in h:
				count += h[s]
				h[s] += 1
			else:
				h[s] = 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		sum_dict = {}
		ans = 0
		ttl = 0
		for i in range(n):
			ttl += arr[i]
			al = []
			if ttl == 0:
				ans += 1
			if ttl in sum_dict:
				al = sum_dict[ttl]
				ans += len(al)
			al.append(i)
			sum_dict[ttl] = al
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		d = {0: 1}
		ans = 0
		m = 0
		for i in range(len(arr)):
			m = m + arr[i]
			if m in d:
				ans += d[m]
			d[m] = d.get(m, 0) + 1
		return ans


from collections import Counter as c

class Solution:

	def findSubArrays(self, arr, n):
		pref = [arr[0]]
		ans = 0
		for i in range(1, n):
			pref.append(pref[-1] + arr[i])
		count = c(pref)
		if 0 not in count:
			count[0] = 0
		count[0] += 1
		for i in count.values():
			ans += i * (i - 1) // 2
		return ans


class Solution:

	def findSubArrays(self, arr, n):
		(x, y) = (0, 0)
		a = {0: 1}
		for i in range(n):
			x += arr[i]
			if x not in a:
				a[x] = 1
			else:
				y += a[x]
				a[x] += 1
		return y


class Solution:

	def findSubArrays(self, arr, n):
		pre_sum = 0
		d = {0: 1}
		count = 0
		for ele in arr:
			pre_sum += ele
			if pre_sum in d:
				count += d[pre_sum]
				d[pre_sum] += 1
			else:
				d[pre_sum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		dic = defaultdict(int)
		dic[0] = 1
		pre_sum = 0
		count = 0
		for elm in arr:
			pre_sum += elm
			count += dic[pre_sum]
			dic[pre_sum] += 1
		return count


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		arr = [0] + arr
		d = defaultdict(int)
		s = 0
		count = 0
		for i in range(n + 1):
			s += arr[i]
			d[s] += 1
			count += d[s] - 1
		return count


class Solution:

	def findSubArrays(self, arr, n):
		res = 0
		mp = dict()
		presum = 0
		mp[presum] = 1
		i = -1
		for i in range(n):
			presum += arr[i]
			if presum in mp:
				res += mp.get(presum)
				mp[presum] = mp.get(presum) + 1
			else:
				mp[presum] = 1
		return res


from collections import Counter

class Solution:

	def findSubArrays(self, arr, n):
		mem = Counter({0: 1})
		su = 0
		ans = 0
		for i in range(n):
			su += arr[i]
			mem[su] += 1
		for i in mem.keys():
			s = mem[i]
			ref = s * (s - 1) // 2
			ans += ref
		return ans


from collections import defaultdict

class Solution:

	def findSubArrays(self, arr, n):
		Sum = 0
		prevSum = defaultdict(lambda : 0)
		res = 0
		currsum = 0
		for i in range(0, n):
			currsum += arr[i]
			if currsum == Sum:
				res += 1
			if currsum - Sum in prevSum:
				res += prevSum[currsum - Sum]
			prevSum[currsum] += 1
		return res


class Solution:

	def findSubArrays(self, arr, n):
		d = {}
		s = 0
		c = 0
		for i in arr:
			s += i
			if s == 0:
				c += 1
			if s not in d:
				d[s] = 1
			else:
				d[s] += 1
		s1 = 0
		for j in d.values():
			if j >= 1:
				s1 += j * (j - 1) // 2
		return s1 + c


class Solution:

	def findSubArrays(self, arr, N):
		prefix_sum_freq = {0: 1}
		total = 0
		count = 0
		for i in arr:
			total += i
			if total in prefix_sum_freq:
				count += prefix_sum_freq[total]
			prefix_sum_freq[total] = prefix_sum_freq.get(total, 0) + 1
		return count