Simple O(n) Solution C++ Using Prefix Sum

google
Tags: #<Tag:0x00007f1823de1ee8>

#1

int Solution::solve(vector &A) {
int n=A.size();
int even_sum=0;
int odd_sum=0;
int es[n];
int os[n];
for(int i=0;i<n;i++)
{
if(i&1)
{
odd_sum+=A[i];
}
else
{
even_sum+=A[i];
}
es[i]=even_sum;
os[i]=odd_sum;
}
int c=0;
for(int i=0;i<n;i++)
{
int esafter=es[n-1]-es[i];
int osafter=os[n-1]-os[i];
if(i==0&&esafter==osafter)
{
c++;
}
else
{
if(esafter+os[i-1]==osafter+es[i-1])
c++;
}
}
return c;
}`