Multiple choice

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,

  1. Takes O (3n) and $\Omega$(2n) time if hashing is permitted
  2. Takes O (n3) and $\Omega$ (n2.5) time in the key comparison model
  3. Takes $\odot$ (n3) time and space
  4. Takes O ($\sqrt{n}$) time only if the sum of the 2n elements is an even number
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Keep practicing — related questions