# Ways to Make a Fair Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ways-to-make-a-fair-array)
Canonical: https://scaleengineer.com/dsa/problems/ways-to-make-a-fair-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Nvidia](https://scaleengineer.com/companies/nvidia), [PhonePe](https://scaleengineer.com/companies/phonepe), [Twilio](https://scaleengineer.com/companies/twilio), [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## 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`_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 <= 105`
* `1 <= nums[i] <= 104`

# Approaches
## Brute Force Simulation
The most straightforward approach is to simulate the process directly. We can iterate through every possible index `i` that can be removed. For each `i`, we construct a new array that excludes `nums[i]`. Then, we iterate through this new array, calculate the sum of its even-indexed elements and odd-indexed elements, and check if they are equal. If they are, we increment a counter. This process is repeated for all possible indices.
**Time:** O(N^2), where N is the length of the input array. The outer loop runs N times. Inside the loop, creating the new list takes O(N) time, and calculating the sums also takes O(N) time. This results in a total complexity of O(N * (N + N)) = O(N^2). · **Space:** O(N), where N is the length of the input array. In each iteration of the outer loop, a new list of size N-1 is created.
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Highly inefficient for large input arrays, leading to a 'Time Limit Exceeded' error on most platforms.; Uses extra space proportional to the input size for each iteration.
### Explanation
This method involves a nested loop structure. The outer loop selects an element to remove, and the inner loop processes the resulting array.

For example, if `nums = [2,1,6,4]`:
1. **Remove index 0:** New array is `[1,6,4]`. Even sum (1+4)=5, Odd sum (6)=6. Not fair.
2. **Remove index 1:** New array is `[2,6,4]`. Even sum (2+4)=6, Odd sum (6)=6. Fair. Increment count.
3. **Remove index 2:** New array is `[2,1,4]`. Even sum (2+4)=6, Odd sum (1)=1. Not fair.
4. **Remove index 3:** New array is `[2,1,6]`. Even sum (2+6)=8, Odd sum (1)=1. Not fair.

The final count is 1.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        int fairCount = 0;

        for (int i = 0; i < n; i++) {
            // Create a temporary list without the element at index i
            List<Integer> tempList = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    tempList.add(nums[j]);
                }
            }

            // Calculate even and odd sums for the temporary list
            int evenSum = 0;
            int oddSum = 0;
            for (int j = 0; j < tempList.size(); j++) {
                if (j % 2 == 0) {
                    evenSum += tempList.get(j);
                } else {
                    oddSum += tempList.get(j);
                }
            }

            // Check if the array is fair
            if (evenSum == oddSum) {
                fairCount++;
            }
        }

        return fairCount;
    }
}
```
### Algorithm
1. Initialize a counter `fairCount` to 0.
2. Iterate through each index `i` from `0` to `n-1`, where `n` is the length of `nums`.
3. For each `i`, create a new temporary list or array by removing the element `nums[i]`.
4. Initialize `evenSum` and `oddSum` to 0.
5. Iterate through the temporary array. For each element at index `j`:
   - If `j` is even, add the element to `evenSum`.
   - If `j` is odd, add the element to `oddSum`.
6. After iterating through the temporary array, check if `evenSum` equals `oddSum`.
7. If they are equal, increment `fairCount`.
8. After the outer loop finishes, return `fairCount`.

## Single Pass with Prefix Sums
Instead of re-calculating sums from scratch in every iteration, we can optimize the process by observing the effect of removing an element `nums[i]`. When `nums[i]` is removed, the array is split into a left part (elements before `i`) and a right part (elements after `i`). The indices in the left part remain unchanged. However, the indices of all elements in the right part decrease by one, which flips their parity (even becomes odd, odd becomes even).

We can pre-calculate the total sum of even-indexed and odd-indexed elements. Then, as we iterate through the array, we can maintain the sums of elements to the left of `i` (`leftEvenSum`, `leftOddSum`). With this information and the total sums, we can deduce the sums of elements to the right of `i` in constant time. This allows us to calculate the new sums after removal and check for fairness in O(1) for each index.
**Time:** O(N), where N is the length of the input array. We perform one pass to compute the total sums and a second pass to check each index for fairness. Both passes are linear, so the total time complexity is O(N) + O(N) = O(N). · **Space:** O(1). We only use a few constant extra variables to store the sums, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Efficiently handles large inputs without performance issues.
**Cons:** The logic is more complex than the brute-force approach and requires careful handling of sums.
### Explanation
This approach avoids creating new arrays and re-scanning. It relies on a clever calculation using prefix and suffix sums.

Let's break down the sums after removing `nums[i]`:
- **New Even Sum**: This will be the sum of elements that end up at an even index. This includes:
  1. Elements at even indices to the left of `i` (`leftEvenSum`).
  2. Elements at odd indices to the right of `i` (since their index `j` becomes `j-1`, which is even).
- **New Odd Sum**: This will be the sum of elements that end up at an odd index. This includes:
  1. Elements at odd indices to the left of `i` (`leftOddSum`).
  2. Elements at even indices to the right of `i` (since their index `j` becomes `j-1`, which is odd).

By iterating once to get totals, and a second time to check each removal, we achieve a linear time solution.

```java
class Solution {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        // Step 1: Calculate total sums for the original array
        int totalEvenSum = 0;
        int totalOddSum = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                totalEvenSum += nums[i];
            } else {
                totalOddSum += nums[i];
            }
        }

        int fairCount = 0;
        int leftEvenSum = 0;
        int leftOddSum = 0;

        // Step 2: Iterate through the array to check each removal
        for (int i = 0; i < n; i++) {
            int rightEvenSum;
            int rightOddSum;

            if (i % 2 == 0) {
                // Current element is at an even index
                rightEvenSum = totalEvenSum - leftEvenSum - nums[i];
                rightOddSum = totalOddSum - leftOddSum;
            } else {
                // Current element is at an odd index
                rightEvenSum = totalEvenSum - leftEvenSum;
                rightOddSum = totalOddSum - leftOddSum - nums[i];
            }

            // After removal, right part's parities are flipped
            // New even sum = left even sum + right odd sum
            // New odd sum = left odd sum + right even sum
            if (leftEvenSum + rightOddSum == leftOddSum + rightEvenSum) {
                fairCount++;
            }

            // Update left sums for the next iteration
            if (i % 2 == 0) {
                leftEvenSum += nums[i];
            } else {
                leftOddSum += nums[i];
            }
        }

        return fairCount;
    }
}
```
### Algorithm
1. First, make a single pass through the entire array to calculate the `totalEvenSum` and `totalOddSum`.
2. Initialize a counter `fairCount` to 0.
3. Initialize `leftEvenSum = 0` and `leftOddSum = 0` to keep track of sums of elements to the left of the current index.
4. Iterate through the array from index `i = 0` to `n-1`.
5. In each iteration, determine the sums of the elements to the right of `i`. Let's say `rightEvenSum` and `rightOddSum`.
   - If `i` is an even index, `rightEvenSum = totalEvenSum - leftEvenSum - nums[i]` and `rightOddSum = totalOddSum - leftOddSum`.
   - If `i` is an odd index, `rightEvenSum = totalEvenSum - leftEvenSum` and `rightOddSum = totalOddSum - leftOddSum - nums[i]`.
6. After removing `nums[i]`, the elements to its right shift their positions, flipping their index parity. The new sums will be:
   - `newEvenSum = leftEvenSum + rightOddSum`
   - `newOddSum = leftOddSum + rightEvenSum`
7. Check if `newEvenSum == newOddSum`. If they are equal, increment `fairCount`.
8. Before moving to the next iteration, update the `left` sums by including the current element `nums[i]`.
   - If `i` is even, `leftEvenSum += nums[i]`.
   - If `i` is odd, `leftOddSum += nums[i]`.
9. Return `fairCount`.

# Solutions
### Java

```java
class Solution {
public
  int waysToMakeFair(int[] nums) {
    int s1 = 0, s2 = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      s1 += i % 2 == 0 ? nums[i] : 0;
      s2 += i % 2 == 1 ? nums[i] : 0;
    }
    int t1 = 0, t2 = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2 ? 1 : 0;
      ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v ? 1 : 0;
      t1 += i % 2 == 0 ? v : 0;
      t2 += i % 2 == 1 ? v : 0;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var waysToMakeFair =
  function (nums) {
    let [s1, s2, t1, t2] = [0, 0, 0, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
      if (i % 2 == 0) {
        s1 += nums[i];
      } else {
        s2 += nums[i];
      }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
      const v = nums[i];
      ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2;
      ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v;
      t1 += i % 2 == 0 ? v : 0;
      t2 += i % 2 == 1 ? v : 0;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int waysToMakeFair(vector<int> &nums) {
    int s1 = 0, s2 = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      s1 += i % 2 == 0 ? nums[i] : 0;
      s2 += i % 2 == 1 ? nums[i] : 0;
    }
    int t1 = 0, t2 = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2;
      ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v;
      t1 += i % 2 == 0 ? v : 0;
      t2 += i % 2 == 1 ? v : 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int: s1, s2 = sum(nums[:: 2]), sum(nums[1:: 2]) ans = t1 = t2 = 0 for i, v in enumerate(nums): ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2 ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v t1 += v if i % 2 == 0 else 0 t2 += v if i % 2 == 1 else 0 return ans

```