 # Largest Span between 2 arrays

#1

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 a[i]+a[i+1]+⋯+a[j]=b[i]+b[i+1]+⋯+b[j] or report that there is no such span,

(i)Takes 0(3^n) and Ω(2^n) time if hashing is permitted
(ii)Takes 0(n^3) and Ω(n^2.5) time in the key comparison mode
(iii)Takes Θ(n) time and space
(iv)Takes O(√n) time only if the sum of the 2n elements is an even number

#2

Ans is option (iii).

Here we are having difference from -n to n so there are 2n+1 possibility of diff.
We are having 2 cases :

1: if index 0 to n is maxLength
2: any subarray having maxLength

For this we are maintaining a diff array and checking if sum in both array is equal then change maxLength.

`````` public static int longestSpan(int arr[],int n,int arr2[])
{
int diff[]=new int[2*n+1];
int maxLen=0,pre1=0,pre2=0;
Arrays.fill(diff,-1);
for(int i=0;i<n;++i)
{
pre1+=arr[i];
pre2+=arr2[i];
int cdiff=pre1-pre2;
//index finded by adding n as max neg val is -n
int diffindex=n+cdiff;
//from 0 to i
if(cdiff==0)
{
maxLen=i+1;
}
else if(diff[diffindex]==-1)
{
diff[diffindex]=i;
}
else
{
maxLen=Math.max(maxLen,i-diff[diffindex]);
}
}
return maxLen;
}``````