C++ solution - using prefix sum , linear space O(n) solution


#1

int Solution::solve(vector &A) {
if(A.size()==1)
return 1;
if(A.size()==2)
{
if(A[0]==A[1])
return 1;
else
return 0;
}
int sum_o=0;
int sum_e=0;
for(int i=0;i<A.size();i++)
{
if(i&1)
sum_o+=A[i];
else
sum_e+=A[i];
}
// cout<<sum_o<<" "<<sum_e<<endl;
int count=0;
int presum_o=0;
int presum_e=0;
for(int i=0;i<A.size();i++)
{

    if(i&1)
    {
        
        int temp_sum_e=sum_o-A[i]+presum_e-presum_o;
        int temp_sum_o=sum_e-presum_e+presum_o;
        if(temp_sum_e==temp_sum_o)
        {
            // cout<<A[i]<<" "<<i<<endl;
            count++;
        }
        presum_o+=A[i];
    }
    else
    {
        
        int temp_sum_o=sum_e-A[i]+presum_o-presum_e;
        int temp_sum_e=sum_o-presum_o+presum_e;
        if(temp_sum_e==temp_sum_o)
        {  
            // cout<<A[i]<<" "<<i<<endl;
            count++;
        }
        presum_e+=A[i];
    }
}
return count;

}