Using prefix sum and suffix Sum intutive c++ solution


#1

Comment body goes here.int Solution::solve(vector &A) {
int n=A.size();
if(n==0)
return 0;
vector<pair<int,int> > left_sum(n),right_sum(n);
left_sum[0].first=A[0];
left_sum[0].second=0;
for(int i=1;i<n;i++)
{
if(i%2==0)
{
left_sum[i].first=left_sum[i-1].first+A[i];
left_sum[i].second=left_sum[i-1].second;
}
else
{
left_sum[i].first=left_sum[i-1].first;
left_sum[i].second=left_sum[i-1].second+A[i];
}
}
if(n%2==0){
right_sum[n-1].first=0;
right_sum[n-1].second=A[n-1];
}
else
{
right_sum[n-1].first=A[n-1];
right_sum[n-1].second=0;
}
for(int i=n-2;i>=0;i–)
{
if(i%2==0)
{
right_sum[i].first=right_sum[i+1].first+A[i];
right_sum[i].second= right_sum[i+1].second;
}
else
{
right_sum[i].first=right_sum[i+1].first;
right_sum[i].second= right_sum[i+1].second+A[i];
}
}
int count=0;
int even=0,odd=0;
for(int i=0;i<n;i++)
{
if(i!=0)
{
even=left_sum[i-1].first;
odd=left_sum[i-1].second;
}
if(i%2==0)
{
int v1=right_sum[i].first-A[i];
int v2=right_sum[i].second;
even+=v2;
odd+=v1;
}
else
{
int v1=right_sum[i].first;
int v2=right_sum[i].second-A[i];
even+=v2;
odd+=v1;
}
if(even==odd)
count++;
}
return count;
}