Given an array containing 0s and 1s. Find the number of subarrays having equal number of 0s and 1s. 
Example 1:
Input:
n = 7
A[] = {1,0,0,1,0,1,1}
Output: 8
Explanation: The index range for the 8 
sub-arrays are: (0, 1), (2, 3), (0, 3), (3, 4), 
(4, 5) ,(2, 5), (0, 5), (1, 6)
Example 2:
Input:
n = 5
A[] = {1,1,1,1,0}
Output: 1
Explanation: The index range for the 
subarray is (3,4).
Your Task:
You don't need to read input or print anything. Your task is to complete the function countSubarrWithEqualZeroAndOne() which takes the array arr[] and the size of the array as inputs and returns the number of subarrays with equal number of 0s and 1s.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
1 <= n <= 10^{6}
0 <= A[i] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Function to count subarrays with 1s and 0s.
    def countSubarrWithEqualZeroAndOne(self,arr, n):
        #Your code here
        

Solutions:
class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		diffmap = {}
		diff = 0
		ans = 0
		for i in range(n):
			if arr[i] == 1:
				diff += 1
			else:
				diff -= 1
			if diff == 0:
				ans += 1
			if diff in diffmap:
				ans += diffmap[diff]
				diffmap[diff] += 1
			else:
				diffmap[diff] = 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		hm = {0: 1}
		ps = 0
		count_subarr = 0
		for i in range(len(arr)):
			if arr[i] == 0:
				ps += -1
			else:
				ps += 1
			if ps not in hm:
				hm[ps] = 1
			else:
				count_subarr += hm[ps]
				hm[ps] += 1
		return count_subarr


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = dict()
		ans = 0
		total = 0
		for i in arr:
			x = -1 if i == 0 else 1
			total += x
			if total == 0:
				ans += 1
			if total in d:
				ans += d[total]
				d[total] += 1
			else:
				d[total] = 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		cnt = 0
		hash = {}
		cur = 0
		for el in arr:
			cur_el = -1 if not el else el
			cur += cur_el
			if cur == 0:
				cnt += 1
			cnt += hash.get(cur, 0)
			hash[cur] = hash.get(cur, 0) + 1
		return cnt


class Solution:

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


class Solution:

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


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		count = 0
		mysum = 0
		d = {}
		for i in arr:
			mysum += i
			if mysum == 0:
				count += 1
			if mysum in d:
				count += d[mysum]
			if mysum in d:
				d[mysum] += 1
			else:
				d[mysum] = 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		(p, q) = (0, 0)
		dic = {0: 1}
		for i in arr:
			if i == 0:
				p += 1
			else:
				q += 1
			dic[p - q] = dic.get(p - q, 0) + 1
		ans = 0
		for i in dic.values():
			ans += (i * i - i) // 2
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		counter = {0: 1}
		subArrays = prefixSUM = 0
		for X in arr:
			prefixSUM += 1 if X == 1 else -1
			subArrays += counter.get(prefixSUM, 0)
			counter[prefixSUM] = counter.get(prefixSUM, 0) + 1
		return subArrays


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {0: 1}
		tot = 0
		sub = 0
		for i in arr:
			if i == 1:
				tot += 1
			else:
				tot -= 1
			if tot in dic:
				sub += dic[tot]
			else:
				dic[tot] = 0
			dic[tot] += 1
		return sub


from collections import *

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		count = 0
		sum_map = defaultdict(int)
		sum_map[0] = 1
		sum_so_far = 0
		for i in range(n):
			sum_so_far += arr[i] if arr[i] == 1 else -1
			count += sum_map[sum_so_far]
			sum_map[sum_so_far] += 1
		return count


from collections import defaultdict

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		dic = defaultdict(int)
		s = 0
		c = 0
		for i in range(n):
			s += arr[i]
			if s == 0:
				c = c + 1
			c = c + dic[s]
			dic[s] += 1
		return c


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		t = 0
		ans = 0
		m = {}
		for i in range(n):
			if t in m:
				m[t] += 1
			else:
				m[t] = 1
			if arr[i]:
				t += 1
			else:
				t -= 1
			if t in m:
				ans += m[t]
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		prefix_sum = 0
		sums = {0: 1}
		count = 0
		for i in range(n):
			prefix_sum += arr[i] * 2 - 1
			if prefix_sum in sums:
				count += sums[prefix_sum]
				sums[prefix_sum] += 1
			else:
				sums[prefix_sum] = 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		counter = 0
		prefix = 0
		d = {0: 1}
		for i in arr:
			prefix += i * 2 - 1
			if prefix in d:
				counter += d[prefix]
				d[prefix] += 1
			else:
				d[prefix] = 1
		return counter


class Solution:

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


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		mp = dict()
		summ = 0
		count = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			summ += arr[i]
			if summ == 0:
				count += 1
			if summ in mp.keys():
				count += mp[summ]
			mp[summ] = mp.get(summ, 0) + 1
		return count


class Solution:

	def solve(self, arr, n, k):
		c = 0
		s = 0
		d = {}
		for i in range(n):
			s += arr[i]
			if s == k:
				c += 1
			if s - k in d:
				c += d[s - k]
			d[s] = d.get(s, 0) + 1
		return c

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		l = []
		for i in arr:
			if not i:
				l.append(-1)
			else:
				l.append(i)
		return self.solve(l, n, 0)


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		count = 0
		sum = 0
		dict = {}
		for i in range(len(arr)):
			if arr[i] == 0:
				arr[i] = -1
			sum += arr[i]
			if sum == 0:
				count += 1
			if sum in dict.keys():
				count += dict[sum]
			dict[sum] = dict.get(sum, 0) + 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		mp = {}
		cur_sum = 0
		count = 0
		for i in range(n):
			if arr[i] == 0:
				cur_sum += -1
			else:
				cur_sum += arr[i]
			mp[cur_sum] = mp.get(cur_sum, 0) + 1
		for (key, value) in mp.items():
			if value > 1:
				count += value * (value - 1) // 2
		if 0 in mp.keys():
			count += mp[0]
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		pre_sum = 0
		count = 0
		for i in range(n):
			pre_sum += arr[i]
			if pre_sum == 0:
				count += 1
			if pre_sum in dic:
				count += dic[pre_sum]
			else:
				pass
			if pre_sum in dic:
				dic[pre_sum] += 1
			else:
				dic[pre_sum] = 1
		return count


class Solution:

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


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		s = 0
		c = 0
		x = {}
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			s += arr[i]
			if s == 0:
				c += 1
			if s in x.keys():
				c += x[s]
			x[s] = x.get(s, 0) + 1
		return c


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		hashmap = {0: 1}
		count = 0
		prefixsum = 0
		for i in range(n):
			if arr[i] == 0:
				prefixsum -= 1
			else:
				prefixsum += 1
			if prefixsum in hashmap:
				count += hashmap[prefixsum]
				hashmap[prefixsum] += 1
			else:
				hashmap[prefixsum] = 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		res = 0
		s = 0
		d = {0: 1}
		for e in arr:
			n = 1 if e == 1 else -1
			s += n
			if s in d:
				res += d[s]
				d[s] = d[s] + 1
			else:
				d[s] = 1
		return res


class Solution:

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


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		count = 0
		csum = 0
		hmap = {}
		for val in arr:
			csum = csum + 1 if val == 1 else csum - 1
			if csum == 0:
				count += 1
			if csum in hmap:
				count += hmap[csum]
			hmap[csum] = hmap.get(csum, 0) + 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		summ = 0
		res = 0
		dic = {}
		for i in range(n):
			summ += arr[i]
			if summ == 0:
				res += 1
			if summ in dic:
				res += dic[summ]
				dic[summ] += 1
			else:
				dic[summ] = 1
		return res


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		count = 0
		diff_map = {0: 1}
		diff = 0
		for i in range(n):
			if arr[i] == 1:
				diff += 1
			else:
				diff -= 1
			if diff in diff_map:
				count += diff_map[diff]
				diff_map[diff] += 1
			else:
				diff_map[diff] = 1
		return count


class Solution:

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


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {}
		su = 0
		c = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			su += arr[i]
			if su == 0:
				c += 1
			if su in dic:
				c += dic[su]
			else:
				dic[su] = 0
			dic[su] += 1
		return c


class Solution:

	def solve(self, arr, n, k):
		c = 0
		s = 0
		d = {}
		for i in range(n):
			s += arr[i]
			if s == k:
				c += 1
			if s - k in d:
				c += d[s - k]
			d[s] = d.get(s, 0) + 1
		return c

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		i = 0
		while i < n:
			if arr[i] == 0:
				arr[i] = -1
			i += 1
		return self.solve(arr, n, 0)


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = {}
		d[0] = 1
		s = 0
		c = 0
		for i in range(n):
			a = arr[i]
			s = s + a
			if 2 * s - (i + 1) in d:
				freq = d[2 * s - (i + 1)]
				d[2 * s - (i + 1)] = d[2 * s - (i + 1)] + 1
				c = freq + c
			else:
				d[2 * s - (i + 1)] = 1
		return c


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for (i, ele) in enumerate(arr):
			if ele == 0:
				arr[i] = -1
		kmap = {0: 1}
		prev = 0
		c = 0
		for ele in arr:
			prev += ele
			if prev not in kmap:
				kmap[prev] = 1
			else:
				c += kmap[prev]
				kmap[prev] += 1
		return c


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(len(arr)):
			if arr[i] == 0:
				arr[i] = -1
		ans = 0
		sm = 0
		k = 0
		d = {0: 1}
		for i in range(len(arr)):
			sm += arr[i]
			if sm - k in d:
				ans += d[sm - k]
			if sm in d:
				d[sm] += 1
			else:
				d[sm] = 1
		return ans


from collections import defaultdict

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = defaultdict(int)
		ans = 0
		tmp = 0
		for i in range(n):
			d[tmp] += 1
			if arr[i]:
				tmp += 1
			else:
				tmp -= 1
			ans = ans + d[tmp]
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		count = 0
		sum = 0
		q = {}
		for i in range(len(arr)):
			sum += -1 if arr[i] == 0 else arr[i]
			if q.get(sum):
				q[sum] += 1
			else:
				q[sum] = 1
		for j in q:
			if q[j] > 1:
				count += q[j] * (q[j] - 1) // 2
		if q.get(0):
			count += q[0]
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		sum = 0
		map = {}
		c = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			sum = sum + arr[i]
			if sum == 0:
				c = c + 1
			if sum in map:
				c = c + map[sum]
			map[sum] = 1 + map.get(sum, 0)
		return c


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		curr_sum = 0
		equal_subarrays_count = 0
		counts_of_each_currentsum = dict()
		counts_of_each_currentsum[0] = 1
		for i in range(0, len(arr)):
			if arr[i] == 1:
				curr_sum = curr_sum + 1
			else:
				curr_sum = curr_sum - 1
			if curr_sum in counts_of_each_currentsum:
				equal_subarrays_count = equal_subarrays_count + counts_of_each_currentsum[curr_sum]
				counts_of_each_currentsum[curr_sum] = counts_of_each_currentsum[curr_sum] + 1
			else:
				counts_of_each_currentsum[curr_sum] = 1
		return equal_subarrays_count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = {0: 1}
		for i in range(n):
			arr[i] = arr[i] - 1 if arr[i] == 0 else arr[i]
			s = 0
		for i in range(n):
			s += arr[i]
			d[s] = d.get(s, 0) + 1
		ans = 0
		for k in d.keys():
			ans += d[k] * (d[k] - 1) // 2
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		m = dict()
		m[0] = 1
		(sum, ans) = (0, 0)
		k = 0
		for i in range(n):
			sum += arr[i]
			if sum - k in m:
				ans = ans + m[sum - k]
			if sum in m:
				m[sum] += 1
			else:
				m[sum] = 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, lis, n):
		d = {}
		s1 = 0
		for i in range(n):
			if lis[i] == 0:
				s1 += -1
			else:
				s1 += lis[i]
			if d.get(s1):
				d[s1] += 1
			else:
				d[s1] = 1
		cnt = 0
		for i in d:
			if d[i] > 1:
				cnt += d[i] * int(d[i] - 1) / 2
		if d.get(0):
			cnt += d[0]
		return int(cnt)


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = {}
		count = 0
		total_sum = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			total_sum += arr[i]
			if total_sum == 0:
				count += 1
			if total_sum in d.keys():
				count += d[total_sum]
			d[total_sum] = d.get(total_sum, 0) + 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {}
		cur_sum = 0
		ans = 0
		for i in range(n):
			cur_sum += 1 if arr[i] == 1 else -1
			if cur_sum == 0:
				ans += 1
			if cur_sum in dic:
				ans += dic[cur_sum]
			dic[cur_sum] = dic.get(cur_sum, 0) + 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dicti = {}
		count = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		for i in range(1, n):
			arr[i] += arr[i - 1]
		for i in arr:
			if i == 0:
				if i in dicti:
					count += dicti[i] + 1
					dicti[i] += 1
				else:
					dicti[i] = 1
					count += 1
			elif i in dicti:
				count += dicti[i]
				dicti[i] += 1
			else:
				dicti[i] = 1
		return count


from collections import defaultdict

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = defaultdict(int)
		s = 0
		result = 0
		d[0] = 1
		for i in arr:
			if i == 1:
				s += 1
			else:
				s -= 1
			if s in d:
				result += d[s]
			d[s] += 1
		return result


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {}
		sum = 0
		ps = []
		ans = 0
		for i in arr:
			if i == 0:
				sum -= 1
			else:
				sum += 1
			ps.append(sum)
		for i in ps:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		if 0 in dic:
			ans += dic[0]
		dic[ps[0]] -= 1
		for i in range(1, n - 1):
			ans += dic[ps[i - 1]]
			dic[ps[i]] -= 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dict1 = dict()
		sum1 = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		count = 0
		for i in range(n):
			sum1 += arr[i]
			if sum1 == 0:
				count += 1
			if sum1 not in dict1:
				dict1[sum1] = 1
			else:
				count += dict1[sum1]
				dict1[sum1] += 1
		return count


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = {0: 1}
		c = 0
		pre_sum = 0
		for item in arr:
			if item == 0:
				item = -1
			pre_sum += item
			if pre_sum in d:
				c += d[pre_sum]
				d[pre_sum] += 1
			else:
				d[pre_sum] = 1
		return c


class Solution:

	def isBalanced(self, ls, n):
		ctr = 0
		for i in range(n):
			if ls[i] == 0:
				ctr -= 1
			else:
				ctr += 1
		return ctr == 0

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		if n == 1:
			return 0
		if n == 2:
			if arr[0] + arr[1] == 1:
				return 1
			return 0
		count = 0
		d = {}
		summ = 0
		for i in range(n):
			summ += -1 if arr[i] == 0 else 1
			if summ == 0:
				count += 1
			if summ in d.keys():
				count += d[summ]
			d[summ] = d.get(summ, 0) + 1
		return count


def sub_arrays_with_given_sum(a, n, sum):
	hm = {}
	prefix_sum = 0
	count = 0
	for i in range(n):
		prefix_sum += a[i]
		if prefix_sum == sum:
			count += 1
		if prefix_sum - sum in hm:
			count += hm.get(prefix_sum - sum)
		if prefix_sum not in hm:
			hm[prefix_sum] = 1
		else:
			hm[prefix_sum] += 1
	return count

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
		return sub_arrays_with_given_sum(arr, n, 0)


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		a1 = {}
		s = 0
		c = 0
		for i in arr:
			if i == 0:
				s -= 1
			else:
				s += 1
			if s == 0:
				c += 1
			if s not in a1:
				a1[s] = 0
			c += a1[s]
			a1[s] += 1
		return c


from collections import defaultdict

class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		d = defaultdict(lambda : 0)
		ans = 0
		d[0] = 1
		su = 0
		for i in range(n):
			if arr[i] == 0:
				arr[i] = -1
			su += arr[i]
			if su not in d.keys():
				d[su] = 1
			else:
				ans += d[su]
				d[su] += 1
		return ans


class Solution:

	def countSubarrWithEqualZeroAndOne(self, arr, n):
		dic = {0: 1}
		ans = 0
		op = 0
		for i in arr:
			if i == 1:
				ans += 1
			else:
				ans -= 1
			if ans in dic:
				op += dic[ans]
				dic[ans] += 1
			else:
				dic[ans] = 1
		return op