##### Gtae2006_54

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

ai+ai+1+...+bj =ai+bi+1+...+bj ,or report that there is not such span,

(A) Takes  O(3n) and  $\Omega$(2n) time if hashing is permitted
(B) Takes  O(n3)  and  $\Omega$(n2.5) time in the key comparison model
(C) Takes  $\Theta$ (n) time and space
(D) Takes O( n) time only if the sum of the 2n elements is an even number

Discuss