# GATE CSE 2006 | Question: 54

13.1k views

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
3

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
n1=n;
n=1;
while(n<=n1)
{
if(Asum == Bsum)
{
i = x;
j = y;
}
if(n%2==1 && y+1 <= n1)
{
y++;
Asum = Asum + A[y];
Bsum = Bsum + B[y];
}
else if (x-1 >=1)
{
x--;
Asum = Asum + A[x];
Bsum = Bsum + B[x];
}
n++;
}

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$.

0
8

A good video for explanation-  .

0
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.
2
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.

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
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.

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.

ago

## Related questions

1
7.6k views
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)$
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)$
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)
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)$