Largest Span between 2 arrays


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


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;
         for(int i=0;i<n;++i)
             int cdiff=pre1-pre2;
//index finded by adding n as max neg val is -n
             int diffindex=n+cdiff;
//from 0 to i
             else if(diff[diffindex]==-1)
         return maxLen;