edited by
28,461 views
66 votes
66 votes

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,

  1. Takes $ O(3^{n})$ and $\Omega(2^{n})$ time if hashing is permitted
  2. Takes $ O(n^{3})$ and $\Omega(n^{2.5})$ time in the key comparison mode
  3. Takes $\Theta (n)$ time and space
  4. Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
edited by

10 Answers

0 votes
0 votes
As per the above question, the algorithms follows in
1. Since there are total n elements, maximum sum is n for both arrays.
2. Difference between two sums varies from -n to n. So there are total 2n + 1 possible values of difference.
3. If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
0 votes
0 votes

Answer is (C)

Algorithm: 

      1. First we subtract anyone of the string from the another (like considering them set position wise).

  1. Now we have to fin the longest subsequence of 0’s in this resultant string.
  2. This can be done in O(n) time and O(n) space.
    ref. https://www.youtube.com/watch?v=_yGf2rxwZlA for that algorithm.

 

Answer:

Related questions