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];
}
}
}
b)Make 4 variables: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];
}
}
}
c)Now search for largest subset by incrementing the
starting position and continue this loop till the size of the array.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 {}
}
}
}
Time complexity of the algorithm in O(N2) because of the double loop of i and
j
No comments:
Post a Comment