Given two arrays of numbers a1,…,an and b1,…,bn where each number is 0 or 1, the fastest algorithm to find the largest span (i,j) such that a[i]+a[i+1]+⋯+a[j]=b[i]+b[i+1]+⋯+b[j] or report that there is no such span,

(i)Takes 0(3^n) and Ω(2^n) time if hashing is permitted

(ii)Takes 0(n^3) and Ω(n^2.5) time in the key comparison mode

(iii)Takes Θ(n) time and space

(iv)Takes O(√n) time only if the sum of the 2n elements is an even number