Longest Span with same Sum in two Binary arrays

Longest Span with same Sum in two Binary arrays

  September 24, 2017    

---

Explanation :

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

Ref:
http://practice.geeksforgeeks.org/problems/longest-span-with-same-sum-in-two-binary-arrays/0

Code:
     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;
     }