Given two binary arrays arr1[] and arr2[] of same size N. Find length of the longest common span [i, j] where j>=i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j]. 
 
Example 1:
Input:
N = 6
Arr1[] = {0, 1, 0, 0, 0, 0}
Arr2[] = {1, 0, 1, 0, 0, 1}
Output: 4
Explanation: The longest span with same
sum is from index 1 to 4 following zero 
based indexing.
 
Your Task:
You don't need to read input or print anything. Complete the function longestCommonSum() which takes two arrays arr1, arr2 and integer n as input parameters and returns the length of the longest common span.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
0 <= Arr1[i], Arr2[i] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Range queries

Starter code: #User function template for Python



class Solution:

	def longestCommonSum(self, arr1, arr2, n): 

		# code here 

Solutions:
class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] = arr1[i] - arr2[i]
		p = 0
		hash = {}
		ans = 0
		for (i, el) in enumerate(arr1):
			p += el
			if p == 0:
				ans = i + 1
			if p in hash:
				ans = max(ans, i - hash[p])
			else:
				hash[p] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = [0] * n
		for i in range(n):
			arr[i] = arr1[i] - arr2[i]
		d = {0: -1}
		ans = 0
		sm = 0
		for i in range(n):
			sm += arr[i]
			if sm in d:
				ans = max(ans, i - d[sm])
			else:
				d[sm] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		maxlen = 0
		dict1 = {}
		diff = 0
		sum1 = 0
		sum2 = 0
		for i in range(n):
			sum1 += arr1[i]
			sum2 += arr2[i]
			diff = sum1 - sum2
			if diff == 0:
				maxlen = i + 1
			if diff not in dict1:
				dict1[diff] = i
			else:
				maxlen = max(maxlen, i - dict1[diff])
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = []
		for i in range(n):
			arr.append(arr1[i] - arr2[i])
		for i in range(1, n):
			arr[i] += arr[i - 1]
		dic = {}
		dic[0] = -1
		l = 0
		for i in range(n):
			if arr[i] in dic.keys():
				l = max(l, i - dic[arr[i]])
			else:
				dic[arr[i]] = i
		return l


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		a = {0: 0}
		s1 = 0
		s2 = 0
		ans = 0
		for i in range(n):
			s1 += arr1[i]
			s2 += arr2[i]
			if s1 - s2 == 0:
				ans = i + 1
			elif s1 - s2 in a:
				ans = max(ans, i - a[s1 - s2])
			elif s1 - s2 not in a:
				a[s1 - s2] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		n = len(arr1)
		diff_arr = [arr1[i] - arr2[i] for i in range(n)]
		for i in range(1, n):
			diff_arr[i] += diff_arr[i - 1]
		max_len = 0
		hm = {}
		for i in range(n):
			psum = diff_arr[i]
			if psum == 0:
				max_len = max(max_len, i + 1)
			if psum not in hm:
				hm[psum] = i
				continue
			max_len = max(max_len, i - hm[psum])
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		pref1 = 0
		pref2 = 0
		targets = {}
		targets[0] = -1
		res = 0
		for i in range(len(arr1)):
			pref1 += arr1[i]
			pref2 += arr2[i]
			pref_diff = pref1 - pref2
			if pref_diff == 0:
				res = max(res, i + 1)
			if pref_diff in targets:
				res = max(res, i - targets[pref_diff])
			else:
				targets[pref_diff] = i
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr3 = [0] * n
		for i in range(n):
			arr3[i] = arr1[i] - arr2[i]
		dic = dict()
		presum = 0
		maxlen = 0
		for i in range(n):
			presum += arr3[i]
			if presum == 0:
				maxlen = i + 1
			if presum in dic:
				maxlen = max(maxlen, i - dic[presum])
			if presum not in dic:
				dic[presum] = i
		return maxlen


class Solution:

	def longestCommonSum(self, a1, a2, n):
		s = []
		s1 = 0
		s2 = 0
		df = {0: -1}
		dl = {}
		ans = 0
		for i in range(n):
			s1 += a1[i]
			s2 += a2[i]
			if s1 == s2:
				ans = 1
			s.append(s1 - s2)
			if s1 - s2 not in df.keys():
				df[s1 - s2] = i
			else:
				dl[s1 - s2] = i
		for i in range(n):
			if s[i] in dl.keys():
				ans = max(ans, dl[s[i]] - df[s[i]])
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		minidx = dict()
		minidx[0] = -1
		ans = 0
		psum = 0
		for i in range(n):
			psum += arr1[i] - arr2[i]
			if psum in minidx:
				ans = max(ans, i - minidx[psum])
			else:
				minidx[psum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(1, n):
			arr1[i] += arr1[i - 1]
			arr2[i] += arr2[i - 1]
		lst = [arr1[i] - arr2[i] for i in range(n)]
		rec = {0: -1}
		ans = 0
		for i in range(n):
			if lst[i] in rec:
				ans = max(ans, i - rec[lst[i]])
			else:
				rec[lst[i]] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		maxi = 0
		p1 = 0
		p2 = 0
		for i in range(n):
			p1 += arr1[i]
			p2 += arr2[i]
			diff = p1 - p2
			if diff == 0:
				maxi = max(i + 1, maxi)
			elif diff not in d.keys():
				d[diff] = i
			else:
				maxi = max(maxi, i - d[diff])
		return maxi


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		maxi = 0
		pre1 = 0
		pre2 = 0
		for i in range(n):
			pre1 += arr1[i]
			pre2 += arr2[i]
			diff = pre1 - pre2
			if diff == 0:
				maxi = max(maxi, i + 1)
			elif diff in d:
				maxi = max(maxi, i - d[diff])
			else:
				d[diff] = i
		return maxi


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		d[0] = -1
		summa = 0
		maxi = 0
		for i in range(n):
			summa += arr1[i] - arr2[i]
			if summa in d:
				maxi = max(maxi, i - d[summa])
			else:
				d[summa] = i
		return maxi


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = [0] * n
		for i in range(n):
			arr[i] = arr1[i] - arr2[i]
		max_span = 0
		ps = 0
		ps_dict = {}
		for i in range(n):
			ps += arr[i]
			if ps == 0:
				max_span = max(max_span, i + 1)
			elif ps in ps_dict:
				max_span = max(max_span, i - ps_dict[ps])
			else:
				ps_dict[ps] = i
		return max_span


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		res = {}
		cur = 0
		maxi = 0
		for i in range(n):
			cur += arr1[i] - arr2[i]
			if arr1[i] - arr2[i] == 0 and maxi == 0:
				maxi = 1
			if cur == 0:
				maxi = i + 1
			if cur in res:
				maxi = max(maxi, i - res[cur])
			else:
				res[cur] = i
		return maxi


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = [0 for i in range(n)]
		for i in range(n):
			arr[i] = arr1[i] - arr2[i]
		hm = {}
		sum = 0
		max_len = 0
		for i in range(n):
			sum += arr[i]
			if sum == 0:
				max_len = i + 1
			if sum in hm:
				max_len = max(max_len, i - hm[sum])
			else:
				hm[sum] = i
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		pre1 = 0
		pre2 = 0
		diff = {}
		diff[0] = -1
		ma = 0
		for i in range(n):
			pre1 += arr1[i]
			pre2 += arr2[i]
			if pre1 - pre2 not in diff:
				diff[pre1 - pre2] = i
			else:
				ma = max(ma, i - diff[pre1 - pre2])
		return ma


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		maxa = 0
		sum1 = 0
		sum2 = 0
		dif = {}
		for i in range(n):
			sum1 += arr1[i]
			sum2 += arr2[i]
			diff = sum1 - sum2
			if diff == 0:
				maxa = i + 1
			elif diff not in dif:
				dif[diff] = i
			else:
				len = i - dif[diff]
				maxa = max(maxa, len)
		return maxa


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		mp = {}
		res = 0
		currsum = 0
		for i in range(n):
			currsum += arr1[i] - arr2[i]
			if arr1[i] - arr2[0] == 0:
				res = max(1, res)
			if currsum == 0:
				res = i + 1
			if currsum in mp:
				res = max(res, i - mp[currsum])
			else:
				mp[currsum] = i
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		h = {}
		p1 = 0
		p2 = 0
		mx = 0
		for i in range(n):
			p1 += arr1[i]
			p2 += arr2[i]
			dif = p1 - p2
			if dif == 0:
				mx = i + 1
			if dif in h:
				mx = max(mx, i - h[dif])
			else:
				h[dif] = i
		return mx


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		max_len = 0
		tot1 = 0
		tot2 = 0
		diff = {}
		for i in range(n):
			tot1 += arr1[i]
			tot2 += arr2[i]
			curr_diff = tot1 - tot2
			if curr_diff == 0:
				max_len = i + 1
			elif curr_diff not in diff:
				diff[curr_diff] = i
			else:
				length = i - diff[curr_diff]
				max_len = max(max_len, length)
		return max_len


class Solution:

	def longestCommonSum(self, a, b, n):
		d = {0: -1}
		res = s = 0
		for (i, (x, y)) in enumerate(zip(a, b)):
			s += x + (-y if y else 0)
			if s not in d:
				d[s] = i
			res = max(res, i - d[s])
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		a = [0] * n
		for i in range(n):
			a[i] = arr1[i] - arr2[i]
		ps = 0
		m = {}
		ans = 0
		for i in range(n):
			ps += a[i]
			if ps == 0:
				ans = i + 1
			if ps in m:
				ans = max(ans, i - m[ps])
			if ps not in m:
				m[ps] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] = arr1[i] - arr2[i]
		dic = {0: -1}
		m = 0
		s = 0
		for i in range(n):
			s += arr1[i]
			if s not in dic:
				dic[s] = i
			else:
				m = max(m, i - dic[s])
		return m


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] = arr1[i] - arr2[i]
		mp = dict()
		mp[0] = -1
		(ans, sum) = (0, 0)
		for i in range(n):
			sum += arr1[i]
			if sum in mp:
				ans = max(ans, i - mp[sum])
			if sum not in mp:
				mp[sum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] = arr1[i] - arr2[i]
		d = {0: -1}
		s = 0
		ans = 0
		for i in range(n):
			s += arr1[i]
			if s in d:
				ans = max(ans, i - d[s])
			if s not in d:
				d[s] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] -= arr2[i]
		m = dict()
		m[0] = -1
		sum = 0
		ans = 0
		for i in range(n):
			sum += arr1[i]
			if sum in m:
				ans = max(ans, i - m[sum])
			else:
				m[sum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr, b, n):
		for i in range(n):
			arr[i] = arr[i] - b[i]
		mp = dict()
		mp[0] = -1
		ans = 0
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum in mp:
				ans = max(ans, i - mp[sum])
			else:
				mp[sum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(len(arr1)):
			arr1[i] = arr1[i] - arr2[i]
		(ans, sum) = (0, 0)
		d = {0: -1}
		k = 0
		for i in range(len(arr1)):
			sum += arr1[i]
			if sum - k in d:
				ans = max(ans, i - d[sum - k])
			else:
				d[sum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = [0] * n
		for i in range(n):
			arr[i] = arr1[i] - arr2[i]
		mydict = dict()
		summ = 0
		max_len = 0
		for i in range(n):
			summ += arr[i]
			if summ == 0:
				max_len = i + 1
			if summ in mydict:
				max_len = max(max_len, i - mydict[summ])
			else:
				mydict[summ] = i
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		max_len = 0
		sum1 = 0
		sum2 = 0
		diff = {}
		for i in range(n):
			sum1 += arr1[i]
			sum2 += arr2[i]
			current_diff = sum1 - sum2
			if current_diff == 0:
				max_len = i + 1
			elif current_diff not in diff:
				diff[current_diff] = i
			else:
				length = i - diff[current_diff]
				max_len = max(max_len, length)
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		temp = [arr1[i] - arr2[i] for i in range(n)]
		mem = {0: -1}
		curr = 0
		ans = 0
		for i in range(n):
			curr += temp[i]
			if curr in mem:
				ans = max(ans, i - mem[curr])
			else:
				mem[curr] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		sum1 = 0
		sum2 = 0
		hm = {}
		ans = 0
		for k in range(n):
			sum1 += arr1[k]
			sum2 += arr2[k]
			diff = sum1 - sum2
			if diff == 0:
				ans = k + 1
			elif diff in hm:
				ans = max(ans, k - hm[diff])
			else:
				hm[diff] = k
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		temp = []
		for i in range(len(arr1)):
			temp.append(arr1[i] - arr2[i])
		pre_sum = 0
		x = {}
		count = 0
		for i in range(len(temp)):
			pre_sum += temp[i]
			if pre_sum == 0:
				count = i + 1
			if pre_sum not in x:
				x[pre_sum] = i
			else:
				count = max(count, i - x[pre_sum])
		return count


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		l = []
		for i in range(len(arr1)):
			l.insert(i, arr1[i] - arr2[i])
		p_sum = 0
		m = 0
		d = dict()
		for i in range(len(l)):
			p_sum += l[i]
			if p_sum == 0:
				m = i + 1
			if p_sum in d:
				m = max(m, i - d[p_sum])
			else:
				d[p_sum] = i
		return m


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {0: -1}
		ls = s1 = s2 = 0
		for i in range(n):
			s1 += arr1[i]
			s2 += arr2[i]
			c = s1 - s2
			if c in d:
				ls = max(ls, i - d[c])
			else:
				d[c] = i
		return ls


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		total1 = total2 = 0
		hmap = {0: -1}
		ans = 0
		for i in range(n):
			total1 += arr1[i]
			total2 += arr2[i]
			if total1 - total2 in hmap:
				ans = max(ans, i - hmap[total1 - total2])
			else:
				hmap[total1 - total2] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = []
		for i in range(len(arr1)):
			arr.append(arr1[i] - arr2[i])
		sm = 0
		dct = {0: -1}
		res = 0
		for i in range(len(arr)):
			sm += arr[i]
			if sm in dct:
				res = max(res, i - dct[sm])
			else:
				dct[sm] = i
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr1[0] = arr1[0] - arr2[0]
		dic = {0: 0}
		for i in range(1, n):
			arr1[i] = arr1[i] - arr2[i]
			arr1[i] = arr1[i] + arr1[i - 1]
		c = 0
		for i in range(n):
			if arr1[i] == 0:
				c = i + 1
			if arr1[i] in dic:
				b = abs(i - dic[arr1[i]])
				c = max(c, b)
			else:
				dic[arr1[i]] = i
		return c


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		cursum = 0
		maxlen = 0
		for i in range(n):
			cursum += arr1[i] - arr2[i]
			if arr1[i] - arr2[i] == 0 and maxlen == 0:
				m = 1
			if cursum == 0:
				maxlen = i + 1
			if cursum in d:
				maxlen = max(maxlen, i - d[cursum])
			else:
				d[cursum] = i
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		maxLen = 0
		presum1 = presum2 = 0
		diff = [-1] * (2 * n + 1)
		for i in range(n):
			presum1 += 1 if arr1[i] == True else 0
			presum2 += 1 if arr2[i] == True else 0
			curr_diff = presum1 - presum2
			diff_index = n + curr_diff
			if curr_diff == 0:
				maxLen = i + 1
			elif diff[diff_index] == -1:
				diff[diff_index] = i
			else:
				length = i - diff[diff_index]
				maxLen = max(maxLen, length)
		return maxLen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		maxlen = 0
		total1 = 0
		total2 = 0
		d = {}
		for i in range(n):
			total1 += arr1[i]
			total2 += arr2[i]
			currdiff = total1 - total2
			if currdiff == 0:
				maxlen = i + 1
			elif currdiff in d:
				maxlen = max(maxlen, i - d[currdiff])
			else:
				d[currdiff] = i
		return maxlen

def convertToBool(arr):
	a = []
	for x in arr:
		if x == '1':
			a.append(True)
		else:
			a.append(False)
	return a
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr1 = input().strip().split()
		arr2 = input().strip().split()
		arr1 = convertToBool(arr1)
		arr2 = convertToBool(arr2)
		ob = Solution()
		ans = ob.longestCommonSum(arr1, arr2, n)
		print(ans)
		tc = tc - 1


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		max_len = 0
		sum1 = 0
		sum2 = 0
		diff = {}
		for i in range(n):
			sum1 += arr1[i]
			sum2 += arr2[i]
			current_diff = sum1 - sum2
			if current_diff == 0:
				max_len = i + 1
			elif current_diff not in diff:
				diff[current_diff] = i
			else:
				length = i - diff[current_diff]
				max_len = max(max_len, length)
		return max_len

def convertToBool(arr):
	a = []
	for x in arr:
		if x == '1':
			a.append(True)
		else:
			a.append(False)
	return a
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr1 = input().strip().split()
		arr2 = input().strip().split()
		arr1 = convertToBool(arr1)
		arr2 = convertToBool(arr2)
		ob = Solution()
		ans = ob.longestCommonSum(arr1, arr2, n)
		print(ans)
		tc = tc - 1


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		diff = [arr1[i] - arr2[i] for i in range(n)]
		(d, end_idx) = ({}, -1)
		tot = max_len = 0
		for i in range(n):
			tot += diff[i]
			if tot == 0:
				(max_len, end_idx) = (i + 1, i)
			if d.get(tot, None) is not None:
				if max_len < i - d[tot]:
					(max_len, end_idx) = (i - d[tot], i)
			else:
				d[tot] = i
		return end_idx + 1 - (end_idx - max_len + 1)


class Solution:

	def longestCommonSum(self, lst1, lst2, n):
		temp = []
		for i in range(len(lst1)):
			temp.append(lst1[i] - lst2[i])
		my_dict = {}
		prefix_sum = 0
		max_len = 0
		for i in range(len(temp)):
			prefix_sum += temp[i]
			if prefix_sum == 0:
				max_len = max(max_len, i + 1)
				my_dict[prefix_sum] = i
			elif prefix_sum in my_dict:
				max_len = max(max_len, i - my_dict[prefix_sum])
			else:
				my_dict[prefix_sum] = i
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		diffArr = [arr1[i] - arr2[i] for i in range(len(arr1))]
		j = 0
		prefSum = 0
		maxLen = 0
		st = {}
		while j < len(arr1):
			prefSum += diffArr[j]
			if prefSum == 0:
				maxLen = max(maxLen, j + 1)
			elif prefSum not in st:
				st[prefSum] = j
			else:
				maxLen = max(maxLen, j - st[prefSum])
			j += 1
		return maxLen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		temp = []
		for i in range(n):
			temp.append(arr1[i] - arr2[i])
		ans = 0
		csum = 0
		d = {}
		for i in range(len(arr1)):
			csum += temp[i]
			if csum == 0:
				ans = i + 1
			elif csum - 0 in d:
				ans = max(ans, i - d[csum - 0])
			if csum not in d:
				d[csum] = i
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		cursum = 0
		mlen = 0
		temp = [0] * n
		for i in range(n):
			temp[i] = arr1[i] - arr2[i]
		for i in range(n):
			cursum += temp[i]
			if cursum == 0:
				mlen = i + 1
			if cursum not in d:
				d[cursum] = i
			if cursum in d:
				mlen = max(mlen, i - d[cursum])
		return mlen
		return mlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		prefix1 = 0
		prefix2 = 0
		maxlen = 0
		diff = dict()
		for i in range(n):
			prefix1 += arr1[i]
			prefix2 += arr2[i]
			diffum = prefix1 - prefix2
			if diffum == 0:
				maxlen = i + 1
			if diffum in diff:
				maxlen = max(maxlen, i - diff[diffum])
			if diffum not in diff:
				diff[diffum] = i
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		temp = [i - j for (i, j) in zip(arr1, arr2)]
		presum = 0
		d = {0: -1}
		maxlen = 0
		for i in range(len(temp)):
			presum = presum + temp[i]
			if presum not in d:
				d[presum] = i
			else:
				maxlen = max(i - d[presum], maxlen)
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		diff = [-1 for i in range(2 * n + 1)]
		s1 = 0
		s2 = 0
		mle = 0
		for i in range(n):
			s1 += arr1[i]
			s2 += arr2[i]
			d = s1 - s2
			index = n + d
			if d == 0:
				mle = i + 1
			elif diff[index] != -1:
				l = i - diff[index]
				if l > mle:
					mle = l
			elif diff[index] == -1:
				diff[index] = i
		return mle


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		maxlen = 0
		presum1 = 0
		presum2 = 0
		diff = {}
		for i in range(n):
			presum1 += arr1[i]
			presum2 += arr2[i]
			sum_diff = presum1 - presum2
			if sum_diff == 0:
				maxlen = i + 1
			elif sum_diff not in diff:
				diff[sum_diff] = i
			else:
				length = i - diff[sum_diff]
				maxlen = max(maxlen, length)
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		res = {}
		cursum = 0
		maxLen = 0
		for i in range(n):
			cursum += arr1[i] - arr2[i]
			if arr1[i] - arr2[i] is 0 and maxLen is 0:
				max_len = 1
			if cursum == 0:
				maxLen = i + 1
			if cursum in res:
				maxLen = max(maxLen, i - res[cursum])
			else:
				res[cursum] = i
		return maxLen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = [None] * n
		for i in range(n):
			arr[i] = arr1[i] - arr2[i]
		curr = 0
		d = {}
		res = 0
		for i in range(n):
			curr += arr[i]
			if curr == 0:
				res = max(res, i + 1)
			if curr in d:
				res = max(res, i - d[curr])
			else:
				d[curr] = i
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		diff1 = diff2 = 0
		maxlen = 0
		diff = {}
		for i in range(n):
			diff1 += arr1[i]
			diff2 += arr2[i]
			curr_diff = diff1 - diff2
			if curr_diff == 0:
				maxlen = i + 1
			elif curr_diff not in diff:
				diff[curr_diff] = i
			else:
				length = i - diff[curr_diff]
				maxlen = max(maxlen, length)
		return maxlen


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			arr1[i] -= arr2[i]
		d = {}
		m = 0
		csum = 0
		for i in range(n):
			csum += arr1[i]
			if csum == 0:
				m = i + 1
			if csum in d:
				m = max(m, i - d[csum])
			else:
				d[csum] = i
		return m


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		(s, t) = (0, 0)
		for i in range(n):
			m = arr1[i] - arr2[i]
			s = s + m
			if s == 0:
				t = max(t, i + 1)
			elif s in d:
				t = max(t, i - d[s])
			else:
				d[s] = i
		return t


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		diff_arr = [0] * n
		for i in range(n):
			diff_arr[i] = arr1[i] - arr2[i]
		d = {}
		prefix_sum = 0
		largest = 0
		for i in range(n):
			prefix_sum += diff_arr[i]
			if prefix_sum == 0:
				largest = i + 1
			if prefix_sum not in d:
				d[prefix_sum] = i
			else:
				largest = max(largest, i - d[prefix_sum])
		return largest


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		d = {}
		psum1 = psum2 = 0
		longest = 0
		for i in range(n):
			psum1 += arr1[i]
			psum2 += arr2[i]
			diff = psum1 - psum2
			if diff == 0:
				longest = i + 1
			if diff not in d:
				d[diff] = i
			else:
				longest = max(longest, i - d[diff])
		return longest


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(n):
			if arr2[i] == 1:
				arr2[i] = -1
		sum1 = 0
		max1 = 0
		d = {}
		for i in range(n):
			sum1 += arr1[i] + arr2[i]
			if sum1 == 0:
				if i + 1 > max1:
					max1 = i + 1
			elif sum1 not in d:
				d[sum1] = i
			else:
				z = i - d[sum1]
				if z > max1:
					max1 = z
		return max1


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = []
		for i in range(n):
			arr.append(arr1[i] - arr2[i])
		dic = {}
		s = 0
		for i in range(n):
			s = s + arr[i]
			arr[i] = s
		for i in arr:
			dic[i] = -1
		for i in range(n):
			if dic[arr[i]] == -1:
				dic[arr[i]] = i
		ans = 0
		for i in range(n):
			if arr[i] == 0:
				ans = max(ans, i + 1)
			else:
				k = dic.get(arr[i], -1)
				if k != -1 and i != k:
					ans = max(ans, i - k)
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		counter = 0
		max_len = 0
		seen_count = {0: -1}
		for i in range(len(arr1)):
			if arr1[i] == 0 and arr2[i] == 1:
				counter -= 1
			elif arr1[i] == 1 and arr2[i] == 0:
				counter += 1
			if seen_count.get(counter) != None:
				max_len = max(i - seen_count[counter], max_len)
			else:
				seen_count[counter] = i
		return max_len


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		mx = 0
		mp = dict()
		mp[0] = -1
		sum = 0
		for i in range(n):
			arr1[i] = arr1[i] - arr2[i]
			sum += arr1[i]
			if sum in mp:
				mx = max(mx, i - mp[sum])
			else:
				mp[sum] = i
		return mx


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		for i in range(len(arr1)):
			arr1[i] = arr1[i] - arr2[i]
		PFS = [0]
		s = 0
		dic = {0: -1}
		ans = 0
		for i in range(len(arr1)):
			s = s + arr1[i]
			if s not in dic:
				dic[s] = i
			else:
				ans = max(ans, i - dic[s])
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		(count, ans) = (0, 0)
		dic = {}
		arr = []
		for (i, j) in zip(arr1, arr2):
			arr.append(i - j)
		for i in range(n):
			count += arr[i]
			if count == 0:
				ans = i + 1
			elif count not in dic:
				dic[count] = i
			elif count in dic:
				ans = max(ans, i - dic[count])
		return ans


class Solution:

	def longestCommonSum(self, A, B, n):
		sumA = [0]
		sumB = [0]
		length = len(A)
		ans = 0
		for i in range(length):
			sumA.append(sumA[-1] + A[i])
			sumB.append(sumB[-1] + B[i])
		diff = [sumAi - sumBi for (sumAi, sumBi) in zip(sumA, sumB)]
		diff_pos = {}
		for (pos, d) in enumerate(diff):
			if d in diff_pos:
				diff_pos[d].append(pos)
			else:
				diff_pos[d] = [pos]
		ans = 0
		for k in diff_pos:
			if len(diff_pos[k]) >= 2:
				if ans < diff_pos[k][-1] - diff_pos[k][0]:
					ans = diff_pos[k][-1] - diff_pos[k][0]
		return ans


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr3 = []
		sum = 0
		mx = 0
		mp = {0: -1}
		zip_object = zip(arr1, arr2)
		for (arr1, arr2) in zip_object:
			arr3.append(arr1 - arr2)
		for i in range(n):
			sum += arr3[i]
			if sum in mp:
				mx = max(mx, i - mp[sum])
			else:
				mp[sum] = i
		return mx


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr3 = []
		pre_sum = 0
		res = 0
		length = 0
		m = {}
		for i in range(n):
			arr3.append(arr1[i] - arr2[i])
		for i in range(n):
			pre_sum += arr3[i]
			if pre_sum == 0:
				res = i + 1
			if pre_sum in m:
				length = i - m[pre_sum]
				if length > res:
					res = length
			if pre_sum not in m:
				m[pre_sum] = i
		return res


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		arr = []
		for i in range(n):
			arr.append(arr1[i] - arr2[i])
		sm = 0
		count = 0
		mx = 0
		d = dict()
		d[0] = -1
		for i in range(n):
			sm += arr[i]
			if sm in d:
				mx = max(mx, i - d[sm])
			if sm not in d:
				d[sm] = i
		return mx


class Solution:

	def longestCommonSum(self, arr1, arr2, n):
		count = 0
		mxVal = 0
		s1 = 0
		s2 = 0
		dif = {}
		for i in range(n):
			s1 = s1 + arr1[i]
			s2 = s2 + arr2[i]
			diff = s1 - s2
			if diff == 0:
				mxVal = i + 1
			elif diff not in dif:
				dif[diff] = i
			else:
				count = i - dif[diff]
				mxVal = max(mxVal, count)
		return mxVal