1
class Solution {
2
 public:
3
  int waysToMakeFair(vector<int> &nums) {
4
    // it looks a quite complicated problem but actually it is not
5
    // the main observation here is when a element is deleted the odd sum after
6
    // the element becomes the evensum and vice versa so we maintain two vectors
7
    // left and right
8
    vector<int> left(2, 0);
9
    vector<int> right(2, 0);
10

11
    // left[0],right[0] stores the sum of even indices elements to the left and
12
    // right side of the element respectively left[1] right[1] stores the sum of
13
    // odd indices elements to the left and right side of the element
14
    // respectively
15

16
    int ans = 0; // stores the result
17
    // first store the odd sum and even sum in right
18
    for (int i = 0; i < nums.size(); i++) {
19
      if (i % 2) {
20
        // odd index
21
        right[1] += nums[i];
22
      } else {
23
        // even index
24
        right[0] += nums[i];
25
      }
26
    }
27

28
    // now traverse through every element in the array and try to remove the
29
    // element  and check does it makes a fair array
30
    for (int i = 0; i < nums.size(); i++) {
31
      // try to remove the element
32
      int currOdd = right[1];
33
      int currEven = right[0];
34
      if (i % 2) {
35
        // odd index , remove it from currOdd
36
        currOdd -= nums[i];
37
        right[1] -= nums[i]; // since it would be no longer to the right
38
      } else {
39
        // even index , remove it from currEven
40
        currEven -= nums[i];
41
        right[0] -= nums[i];
42
      }
43
      // now check whether the total oddSum and the evenSum in the array are
44
      // equal ? since we are deleting this element oddSum becomes evenSum and
45
      // evenSum becomes oddSum check leftOdd+rightOdd==rightEven+leftEven
46
      // left[0] is even sum to left of i
47
      // left[1] is the odd sum to left of i
48
      if (left[0] + currOdd == left[1] + currEven) ans++;
49
      // since we traverse to right add this value to the left array
50
      (i % 2) ? left[1] += nums[i] : left[0] += nums[i];
51
    }
52

53
    return ans;
54
  }
55
};