Answer is (C). Following algorithm would do.
Since array is binary, the max sum will go until $n$ and so the sum difference of the two arrays can vary between $-n$ and $n$. We use array $start$ to keep the starting index of each possible sum (hence of size $2n+1$) and array $end$ to keep the ending index (these two arrays work like hash tables and since we have only $2n+1$ possible keys, we can do a perfect hashing). So, our required solution will be $max(end[i]-start[i])$ provided both are assigned values.
The algorithm works as follows:
- Initialize $diff$ array to contain the difference of sum of elements of array a and b. i.e., $diff[i] = \sum_{i=0}^n a[i] - b[i]$.
- Now $diff[i]$ can have values from $-n$ to $n$ which gives $2n+1$ possible values and the first occurrence of a $diff$ value marks the beginning of a span and the last occurrence marks the end. We use $start$ and $end$ array for storing these two positions for the $2n+1$ possible values.
- Now, the largest value of $end[i] - start[i]$ for any $i$, will be the largest span and the start of it will be $start[i] + 1$, and end will be $end[i]$. If the span is starting from first position itself (arrays $a$ and $b$ have same first elements), then it will start from $start[i]$ itself.
#include <stdio.h>
#define size 100 //assume n is less than 100
int main()
{
int n, a[size], b[size];
int start[2*size+1], end[2*size+1];
int sum1 = 0, sum2 = 0, i;
int diff[size];
printf("Enter n: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("Enter a[%d]: ", i);
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++)
{
printf("Enter b[%d]: ", i);
scanf("%d", &b[i]);
}
for(i = 0; i < n; i++)
{
if(a[i]) sum1++;
if(b[i]) sum2++;
diff[i] = sum1 - sum2;
}
for(i = 0; i < 2*n; i++)
start[i] = -1,end[i] = -1;
start[n] = end[n] = 0;
//initially sum is 0 at the beginning of array and
//the first n-1 elements of start and end are used
//if sum of A till ith element is less than sum of B till ith element
for(i=0; i < n; i++)
{
if(start[diff[i] + n] == -1)//interested only in the first occurrence of diff[i]
start[diff[i] + n] = i;
end[diff[i] + n] = i;//interested in the last occurrence of diff[i]
}
int max = -1;
int savei = -1; //savei is for storing the sum having the largest span
for(i = 0; i < 2*n; i++)
{
if(start[i] > -1 && (end[i] - start[i] > max))
{
max = end[i] - start[i];
savei = i;
}
}
if(savei >= 0)
{
printf("The largest span is from %d to %d\n", start[savei]+(savei != n), end[savei]);
//when sum zero is having the largest span, span starts from first element itself.
//Else, the span starts from the next element from which the span does not change
}
else
{
printf("No span\n");
}
}