<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:
    def waysToMakeFair(self, nums: List[int]) -> int:
        # Brute Force Approach O(N^2)  69/105 passed and TLE
        '''n=len(nums)
        cnt=0
        for i in range(n):
            # I am deciding to remove index-i now
            # to the left of i odd index is odd and even is even
            # to the right of i odd will be even and even will be odd
            l=i-1
            r=i+1
            sum_odd,sum_even=0,0
            while l>=0:
                if l%2==0:
                    sum_even+=nums[l]
                else:
                    sum_odd+=nums[l]
                l-=1
            while r<n:
                if(r%2==0):
                    sum_odd+=nums[r]
                else:
                    sum_even+=nums[r]
                r+=1
            if sum_odd==sum_even:
                cnt+=1
        return cnt'''

        # Approach-2 O(N)

        # find out the even sum and the odd sum from left and also from right

        even_sum_left=[]
        even_sum_right=[]
        odd_sum_left=[]
        odd_sum_right=[]

        e,o=0,0
        n=len(nums)
        for i in range(n):
            if(i%2==0):
                e+=nums[i]
            else:
                o+=nums[i]
            even_sum_left.append(e)
            odd_sum_left.append(o)

        e,o=0,0
        for i in range(n-1,-1,-1):
            if(i%2==0):
                e+=nums[i]
            else:
                o+=nums[i]
            odd_sum_right.append(o)
            even_sum_right.append(e)

        odd_sum_right=odd_sum_right[::-1]
        even_sum_right=even_sum_right[::-1]

        # print(odd_sum_left)
        # print(odd_sum_right)
        # print(even_sum_left)
        # print(even_sum_right)
        
        ans=0
        for i in range(n):
            a,b,c,d=odd_sum_left[i]-nums[i],odd_sum_right[i]-nums[i],even_sum_left[i]-nums[i],even_sum_right[i]-nums[i]

            if(b+c==a+d):
                ans+=1
        return ans
29300