 # O(n) solution using cumulative sum

#1

. Create a cumulative sum array with odd and even sums to calculate partial even , odd sums. When an element is removed the odd indices after it become even and even indices after it become odd. Depending on the index of the element removed,

if index removed is even,
new esum = esum_pre (sum of all even indices inclusive of element removed) + osum_post(sum of all odd indices after the position removed) - element removed

new osum = osum_pre(sum of all odd indices before removed position) + esum_post(sum of all even elements after the removed position inclusive)

if index removed is odd,
new esum = esum_pre - esum_post
new osum = osum_pre + esum_post - element removed

int Solution::solve(vector &A) {

``````vector<int> cumsum(A.size(), 0); //create a cumulative sum array that
//holds sum of odd, even positions of previous values inclusive

int count = 0, esum = 0, osum = 0, esumtot = 0, osumtot = 0;
cumsum = A;
cumsum = A;
for(int i = 2; i < A.size(); ++i)
cumsum[i] = cumsum[i -2] + A[i] ;

//depending on size of input array the total odd sum and the total odd sum
//will be in different position of cumsum array
if(A.size() & 1)
{osumtot = cumsum[A.size() - 2]; esumtot = cumsum[A.size() - 1];}
else
{osumtot = cumsum[A.size() - 1]; esumtot = cumsum[A.size() - 2];}

int pre;
for(int i = 0; i < A.size(); ++i)
{
if(i == 0) pre = 0;  //when considering removing first index we set previous sum to
//be zero
else pre = cumsum[i - 1];

//iterate over each positon to find esum and osum when that index is removed
if(i & 1)
{
esum = pre + (osumtot - cumsum[i]);
osum = cumsum[i] + (esumtot - pre) - A[i];
}
else
{
esum = cumsum[i] + (osumtot - pre) - A[i];
osum = pre + (esumtot - cumsum[i]);
}

if(esum == osum) count++;
}
return count;
}
``````

I still have a hunch that this could be solved with maps but i am not sure.