We are given with two arrays A and B. Each of size N. Elements of array 
contains either 1 or 0. We have to find such an interval 
(p,q)(inclusive) such that the sum of all the elements of A (between 
this interval) and sum of all elements of B (between this interval ) is 
equal.
i.e. 
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
Solution:
a)Calculate the prefix sum of both the arrays รข€“ value at each index represents the sum till that index
size: to keep track of largest subset size found till now sum: sum of that subset
p: starting index of the subset
q: ending index of the subset
Initially search of there is any sub set from starting index in both the arrays that has the same sum, if found update the value of size, sum and indices p, q.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
Solution:
a)Calculate the prefix sum of both the arrays รข€“ value at each index represents the sum till that index
  void prefixSum(int *array, int *sum)
{
     int i;
     for(i=0;i < N;i++)
     { 
             if(i==0) 
             {
                sum[i]=array[i];
             }
             else
             {
                 sum[i]=array[i]+sum[i-1];
             }
     }
}size: to keep track of largest subset size found till now sum: sum of that subset
p: starting index of the subset
q: ending index of the subset
Initially search of there is any sub set from starting index in both the arrays that has the same sum, if found update the value of size, sum and indices p, q.
for(int i=0;i < N;i  )
    {
            if(sumA[i]==sumB[i])
            {
                          if((i 1) > size)
                          {
                                        size=i 1;
                                        p=0;
                                        q=i;
                                        sum=sumA[i];
                          }
            }
    }for(int i=0;i < N-1;i  )
    {
            for(int j=i 1;j < N;j  )
            {
                    if( (sumA[j]-sumA[i]) == (sumB[j]-sumB[i]) )
                    {
                          if( (j-i) > size )
                          {
                              size= j-i;
                              p=i 1;
                              q=j;
                              sum=sumA[j]-sumA[i];
                          }
                          else if( (j-i) == size )
                          {
                               if( (sumA[j]-sumA[i]) > sum )
                                   sum=(sumA[j]-sumA[i]);
                          }
                          else {}
                    }
            }
    } 
No comments:
Post a Comment