Log In
52 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
in Algorithms
edited by

i = -1, j = -1 //keeps track of longest span i = left index and j = right index

Suppose we have an Array indexed as A[1....n] and B[1....n]

x = n/2 +1 , y= n/2+1 //used to span the arrays x = left and y = right

Asum = A[x]; // sum obtained while spanning array A
Bsum = B[y]; // sum obtained while spanning array B
    if(Asum == Bsum)
        i = x;
        j = y;
    if(n%2==1 && y+1 <= n1)
        Asum = Asum + A[y];
        Bsum = Bsum + B[y];
    else if (x-1 >=1)
        Asum = Asum + A[x];
        Bsum = Bsum + B[x];

If i=-1 and j =-1 then no such span 

else i,j gives the index values

Takes Θ(n) time for spanning array and Θ(n) space for storing arrays

Answer is $C$.


A good video for explanation-  .

I think your algorithm is wrong. it will not find largest span. for ex- if arrays are A[1....6]=[0,0,0,0,1,1] and B[1....6]=[1,1,1,1,1,1]. then largest span should be from index 5 to 6. This algorithm can't find this span at all.
another very nice ques from gate 2006.

i heard that gate 2006 was one of the toughest papers set by GATE and AIR 1 in 2006 paper got even less than 50% marks.

11 Answers

0 votes
Here we can use a prefix sum algorithm

like array a[0-n] and b[0-n] let n = 5

content of a = [1,0,0,1,0] and b = [1,0,1,1,0]

after applying prefix sum we will get

a =[1,1,1,2,2] b = [1,1,2,3,3] which will take O(n)

now we will compare a[n-1] and b[n-1] so here a[n-1] is smaller so we will find the a[n-1] in b if we found it we can return te largest span
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

Answer is (C)


      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. for that algorithm.



Related questions

46 votes
7 answers
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using a right to left pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$
asked Sep 17, 2014 in Algorithms Rucha Shelke 7.6k views
28 votes
10 answers
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$
asked Sep 17, 2014 in Algorithms Rucha Shelke 9.6k views
32 votes
3 answers
Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array, void xyz(int a[], int b [], int c []){ int i,j,k; i=j=k=0; while ((i<n) && (j<m)) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } ... if $i=n$ $i<n,k=m+i-1$ and $b[m-1]\leq a[i]$ if $j=m$ only (i) only (ii) either (i) or (ii) but not both neither (i) nor (ii)
asked Sep 26, 2014 in Algorithms Rucha Shelke 6.9k views
14 votes
4 answers
A set $X$ can be represented by an array $x[n]$ as follows: $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}$ Consider the following algorithm in which $x$, $y$, and $z$ are Boolean arrays of size $n$: algorithm zzz(x[], y[], z[]) { int i; ... y[i]); } The set $Z$ computed by the algorithm is: $(X\cup Y)$ $(X\cap Y)$ $(X-Y)\cap (Y-X)$ $(X-Y)\cup (Y-X)$
asked Sep 26, 2014 in Algorithms Rucha Shelke 2.5k views