Q54

MCQ2 marks, −0.5

Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,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}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or report that there is not such span,

(A)

Takes $O(3^{n})$ and $\Omega(2^{n})$ time if hashing is permitted

(B)

Takes $O(n^{3})$ and $\Omega(n^{2.5})$ time in the key comparison mode

(C)

Takes $\Theta (n)$ time and space

(D)

Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

Loading…