<p>You are given an integer array&nbsp;<code>nums</code>. You can choose <strong>exactly one</strong> index (<strong>0-indexed</strong>) and remove the element. Notice that the index of the elements may change after the removal.</p>

<p>For example, if <code>nums = [6,1,7,4,1]</code>:</p>

<ul>
	<li>Choosing to remove index <code>1</code> results in <code>nums = [6,7,4,1]</code>.</li>
	<li>Choosing to remove index <code>2</code> results in <code>nums = [6,1,4,1]</code>.</li>
	<li>Choosing to remove index <code>4</code> results in <code>nums = [6,1,7,4]</code>.</li>
</ul>

<p>An array is <strong>fair</strong> if the sum of the odd-indexed values equals the sum of the even-indexed values.</p>

<p>Return the <em><strong>number</strong> of indices that you could choose such that after the removal, </em><code>nums</code><em> </em><em>is <strong>fair</strong>. </em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,6,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
Remove index 0: [1,6,4] -&gt; Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -&gt; Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -&gt; Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -&gt; Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong>&nbsp;You can remove any index and the remaining array is fair.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;You cannot make a fair array after removing any index.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
  int waysToMakeFair(vector<int> &nums) {

    // Approach 1: For each index, we calculate the sum after removal in O(n)
    // Time: O(n^2)
    // Spce: O(1)
    // Appraoch 2: Precalculate the sum
    // When removing 1 given index, the sum of even and odd indices of suffix
    // array is swaped
    // Using 4 arrays: oddPrefixSum, evenPrefixSum, oddSuffixSum, evenSuffixSum
    // Precalculate them in O(n)
    // For each index, since the even/odd of indices are swaped in suffix:
    // sumOdd = oddPrefixSum[idx-1] + evenSuffixSum[idx+1]
    // sumEven = evenPrefixSum[idx-1] + oddSuffixSum[idx+1]

    int answer = 0;
    int n = nums.size();
    vector<int> oddPrefixSum(n, 0), oddSuffixSum(n, 0), evenPrefixSum(n, 0),
        evenSuffixSum(n, 0);

    for (int idx = 0; idx < n; ++idx) {
      evenPrefixSum[idx] = (idx == 0 ? 0 : evenPrefixSum[idx - 1]);
      oddPrefixSum[idx] = (idx == 0 ? 0 : oddPrefixSum[idx - 1]);
      if (idx % 2 == 0) {
        evenPrefixSum[idx] += nums[idx];
      } else {
        oddPrefixSum[idx] += nums[idx];
      }
    }

    for (int idx = n - 1; idx >= 0; --idx) {
      oddSuffixSum[idx] = (idx == n - 1 ? 0 : oddSuffixSum[idx + 1]);
      evenSuffixSum[idx] = (idx == n - 1 ? 0 : evenSuffixSum[idx + 1]);

      if (idx % 2 == 0) {
        evenSuffixSum[idx] += nums[idx];
      } else {
        oddSuffixSum[idx] += nums[idx];
      }
    }

    for (int idx = 0; idx < n; ++idx) {
      int sumOdd = (idx == 0 ? 0 : oddPrefixSum[idx - 1]) +
                   (idx == n - 1 ? 0 : evenSuffixSum[idx + 1]);
      int sumEven = (idx == 0 ? 0 : evenPrefixSum[idx - 1]) +
                    (idx == n - 1 ? 0 : oddSuffixSum[idx + 1]);

      if (sumOdd == sumEven) {
        answer++;
      }
    }

    return answer;
  }
};
114500