leetcode 1664 - Ways to Make a Fair Array

https://leetcode.com/problems/ways-to-make-a-fair-array/

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 is fair.

Example 1:

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:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.
Example 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

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int size = nums.size();

vector<vector<int>> left(size + 1, vector<int>(2));
vector<vector<int>> right(size + 1, vector<int>(2)); //{even, odd}
left[0] = {0, 0};
right[0] = {0, 0};

for (int len = 1; len <= size; len++) {
int i = len - 1;
int j = size - len;

if (i % 2 == 0) {
left[len][0] = left[len-1][0] + nums[i];
left[len][1] = left[len-1][1];
} else {
left[len][0] = left[len-1][0];
left[len][1] = left[len-1][1] + nums[i];
}

if (j % 2 == (size - 1) % 2) {
right[len][0] = right[len-1][0] + nums[j];
right[len][1] = right[len-1][1];
} else {
right[len][0] = right[len-1][0];
right[len][1] = right[len-1][1] + nums[j];
}
}

int total = 0;

for (int i = 0; i < size; i++) {
int len = size - i - 1; //right len
int even, odd;

if (i % 2 == 0) {
even = right[len][!(len % 2)];
odd = right[len][len % 2];
} else {
even = right[len][(len % 2)];
odd = right[len][!(len % 2)];
}

even += left[i][0];
odd += left[i][1];

if (even == odd)
total++;
}

return total;
}
};