Given two arrays of numbers a₁,..........., a_n and b₁,............, b_n 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 not such span,

Question

Multiple choice

Takes $\Theta$(3ⁿ) and $\Omega$(2ⁿ) time if hashing is permitted
Takes $\Theta$(n³) and $\Omega$ (n^2.5) time in the key comparison model
Takes $\Theta$($\sqrt{n}$) time only if the sum of the 2n elements is an even number

Reveal answer Fill a bubble to check yourself

Accepted Answer

Takes $\Theta$(n³) time and space

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 + .........+ aj = bi + bi + 1 +...........+ bj or report that there is not such span,