GATE 2006 : 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
#include <stdio.h>
#include <malloc.h>
void printArray(int *a, int start, int end)
{
while(start++ <= end)
printf("%d ", a[start-1]);
printf("\n");
}
void changeStartEnd(int *a, int *b, int *start, int *end, int *sum, int *next1)
{//O(1)
if(b[*start]==1 && a[*start]==0)
++*start;
else if(b[*end]==1 && a[*end]==0)
--*end;
else if(b[*start]==a[*start])
++*start;
else if(b[*end]==a[*end])
--*end;
else if(next1[sum[*end-1]] > next1[sum[*start]])
--*end;
else
++*start;
}
void largestSpan(int *a, int *b, int n)
{
int *sumA = malloc(n*sizeof(int));
int *sumB = malloc(n*sizeof(int));
int *next1A = malloc(n*sizeof(int));
int *next1B = malloc(n*sizeof(int));
int *onePtrA = malloc(n*sizeof(int));
int *onePtrB = malloc(n*sizeof(int));
int i, j, k, start=1, end=n-1, diffA, diffB;
sumA[0]=0; sumB[0]=0;
for (i=1, k=1, j=1; i<n ;i++)
{
sumA[i]=sumA[i-1]+a[i];
sumB[i]=sumB[i-1]+b[i];
if(a[i]==1)
onePtrA[k++]=i;
if(b[i]==1)
onePtrB[j++]=i;
} //O(n)
for(i=1; i<k-1; i++)//O(n)
next1A[i]=sumB[onePtrA[i+1]-1]-sumB[onePtrA[i]];
for(i=1; i<j-1; i++)//O(n)
next1B[i]=sumA[onePtrB[i+1]-1]-sumA[onePtrB[i]];
for(i=1; i<n; i++)
{
diffA=sumA[end]-sumA[start-1];
diffB=sumB[end]-sumB[start-1];
if(diffA == diffB)
break;
if (diffB > diffA)
changeStartEnd(a, b, &start, &end, sumA, next1A);//O(1)
else
changeStartEnd(b, a, &start, &end, sumB, next1B);//O(1)
}//O(n)
printf("%d, %d\n", start, end);
printArray(a, start, end);
printArray(b, start, end);
}
void main()
{
int b[14]={0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1}; // One based indexing
int a[14]={0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0}; // One based indexing
largestSpan(a, b, 14);
}
Hence it takes
ϴ(n) time and space