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

0Comment