Simple solution O(n) time and O(n) space complexity


#1

int Solution::solve(vector &A){
int n = A.size();
if(n==1)return 1;
if(n==2){
if(A[0]==0 && A[1]==0)return 2;
if(A[0]==0 || A[1]==0)return 1;
return 0;
}
vector even_b4(n,0);
vector odd_b4(n,0);
vector even_a4(n,0);
vector odd_a4(n,0);
even_b4[1] = A[0];
odd_b4[1] = 0;
for(int i=2;i<n;i++){
if(i%2==0){
even_b4[i] = even_b4[i-2]+A[i-2];
odd_b4[i] = odd_b4[i-1]+A[i-1];
}
else{
even_b4[i] = even_b4[i-1]+A[i-1];
odd_b4[i] = odd_b4[i-2]+A[i-2];
}
}
if(n%2==0){
even_a4[n-2] = 0;
odd_a4[n-2] = A[n-1];
}
else{
even_a4[n-2] = A[n-1];
odd_a4[n-2] = 0;
}
for(int i=n-3;i>=0;i–){
if(i%2==0){
even_a4[i] = even_a4[i+2]+A[i+2];
odd_a4[i] = odd_a4[i+1]+A[i+1];
}
else{
even_a4[i] = even_a4[i+1]+A[i+1];
odd_a4[i] = odd_a4[i+2]+A[i+2];
}
}
int ct = 0;
for(int i=0;i<n;i++){
int eve_sum = even_b4[i] + odd_a4[i];
int odd_sum = odd_b4[i] + even_a4[i];
if(eve_sum==odd_sum)ct++;
}
return ct;
}