Problem

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

  • Choosing to remove index 1 results in nums = [6,7,4,1].
  • Choosing to remove index 2 results in nums = [6,1,4,1].
  • Choosing to remove index 4 results in nums = [6,1,7,4].

An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the _number of indices that you could choose such that after the removal, _nums ___isfair. _

Examples

Example 1

1
2
3
4
5
6
7
8

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

Example 2

1
2
3

Input: nums = [1,1,1]
Output: 3
Explanation:  You can remove any index and the remaining array is fair.

Example 3

1
2
3

Input: nums = [1,2,3]
Output: 0
Explanation:  You cannot make a fair array after removing any index.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Solution

Method 1 – Prefix Sums and Index Parity

Intuition

When removing an element, the parity (even/odd) of indices after it flips. We can precompute prefix sums for even and odd indices, and for each removal, calculate the new even and odd sums efficiently.

Approach

  1. Compute prefix sums for even and odd indices.
  2. For each index, calculate:
    • Even sum after removal = even sum before i + odd sum after i
    • Odd sum after removal = odd sum before i + even sum after i
  3. If the two sums are equal, increment the answer.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        int n = nums.size();
        vector<int> even(n+1), odd(n+1);
        for (int i = 0; i < n; ++i) {
            even[i+1] = even[i];
            odd[i+1] = odd[i];
            if (i % 2 == 0) even[i+1] += nums[i];
            else odd[i+1] += nums[i];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int evenSum = even[i] + odd[n] - odd[i+1];
            int oddSum = odd[i] + even[n] - even[i+1];
            if (evenSum == oddSum) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func waysToMakeFair(nums []int) int {
    n := len(nums)
    even := make([]int, n+1)
    odd := make([]int, n+1)
    for i := 0; i < n; i++ {
        even[i+1] = even[i]
        odd[i+1] = odd[i]
        if i%2 == 0 {
            even[i+1] += nums[i]
        } else {
            odd[i+1] += nums[i]
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        evenSum := even[i] + odd[n] - odd[i+1]
        oddSum := odd[i] + even[n] - even[i+1]
        if evenSum == oddSum {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        int[] even = new int[n+1], odd = new int[n+1];
        for (int i = 0; i < n; i++) {
            even[i+1] = even[i];
            odd[i+1] = odd[i];
            if (i % 2 == 0) even[i+1] += nums[i];
            else odd[i+1] += nums[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int evenSum = even[i] + odd[n] - odd[i+1];
            int oddSum = odd[i] + even[n] - even[i+1];
            if (evenSum == oddSum) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun waysToMakeFair(nums: IntArray): Int {
        val n = nums.size
        val even = IntArray(n+1)
        val odd = IntArray(n+1)
        for (i in 0 until n) {
            even[i+1] = even[i]
            odd[i+1] = odd[i]
            if (i % 2 == 0) even[i+1] += nums[i] else odd[i+1] += nums[i]
        }
        var ans = 0
        for (i in 0 until n) {
            val evenSum = even[i] + odd[n] - odd[i+1]
            val oddSum = odd[i] + even[n] - even[i+1]
            if (evenSum == oddSum) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from typing import List
class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        n = len(nums)
        even = [0]*(n+1)
        odd = [0]*(n+1)
        for i in range(n):
            even[i+1] = even[i]
            odd[i+1] = odd[i]
            if i % 2 == 0:
                even[i+1] += nums[i]
            else:
                odd[i+1] += nums[i]
        ans = 0
        for i in range(n):
            evenSum = even[i] + odd[n] - odd[i+1]
            oddSum = odd[i] + even[n] - even[i+1]
            if evenSum == oddSum:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn ways_to_make_fair(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut even = vec![0; n+1];
        let mut odd = vec![0; n+1];
        for i in 0..n {
            even[i+1] = even[i];
            odd[i+1] = odd[i];
            if i % 2 == 0 {
                even[i+1] += nums[i];
            } else {
                odd[i+1] += nums[i];
            }
        }
        let mut ans = 0;
        for i in 0..n {
            let even_sum = even[i] + odd[n] - odd[i+1];
            let odd_sum = odd[i] + even[n] - even[i+1];
            if even_sum == odd_sum {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    waysToMakeFair(nums: number[]): number {
        const n = nums.length;
        const even = new Array(n+1).fill(0);
        const odd = new Array(n+1).fill(0);
        for (let i = 0; i < n; i++) {
            even[i+1] = even[i];
            odd[i+1] = odd[i];
            if (i % 2 === 0) even[i+1] += nums[i];
            else odd[i+1] += nums[i];
        }
        let ans = 0;
        for (let i = 0; i < n; i++) {
            const evenSum = even[i] + odd[n] - odd[i+1];
            const oddSum = odd[i] + even[n] - even[i+1];
            if (evenSum === oddSum) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array twice, once for prefix sums and once for checking each index.
  • 🧺 Space complexity: O(n) — For the prefix sum arrays.