Code Implementation

class Solution:
    def waysToMakeFair(self, nums):
        n = len(nums)
        total_even = 0
        total_odd = 0
        for i in range(n):
            if i % 2 == 0:
                total_even += nums[i]
            else:
                total_odd += nums[i]
        res = 0
        left_even = 0
        left_odd = 0
        for i in range(n):
            if i % 2 == 0:
                total_even -= nums[i]
            else:
                total_odd -= nums[i]
            if left_even + total_odd == left_odd + total_even:
                res += 1
            if i % 2 == 0:
                left_even += nums[i]
            else:
                left_odd += nums[i]
        return res
      

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        int n = nums.size();
        int total_even = 0, total_odd = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                total_even += nums[i];
            else
                total_odd += nums[i];
        }
        int res = 0, left_even = 0, left_odd = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                total_even -= nums[i];
            else
                total_odd -= nums[i];
            if (left_even + total_odd == left_odd + total_even)
                ++res;
            if (i % 2 == 0)
                left_even += nums[i];
            else
                left_odd += nums[i];
        }
        return res;
    }
};
      

class Solution {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        int totalEven = 0, totalOdd = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                totalEven += nums[i];
            else
                totalOdd += nums[i];
        }
        int res = 0, leftEven = 0, leftOdd = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                totalEven -= nums[i];
            else
                totalOdd -= nums[i];
            if (leftEven + totalOdd == leftOdd + totalEven)
                ++res;
            if (i % 2 == 0)
                leftEven += nums[i];
            else
                leftOdd += nums[i];
        }
        return res;
    }
}
      

var waysToMakeFair = function(nums) {
    let n = nums.length;
    let totalEven = 0, totalOdd = 0;
    for (let i = 0; i < n; ++i) {
        if (i % 2 === 0)
            totalEven += nums[i];
        else
            totalOdd += nums[i];
    }
    let res = 0, leftEven = 0, leftOdd = 0;
    for (let i = 0; i < n; ++i) {
        if (i % 2 === 0)
            totalEven -= nums[i];
        else
            totalOdd -= nums[i];
        if (leftEven + totalOdd === leftOdd + totalEven)
            res++;
        if (i % 2 === 0)
            leftEven += nums[i];
        else
            leftOdd += nums[i];
    }
    return res;
};
      

Problem Description

Given an integer array nums, you are to remove exactly one element from the array. After removal, an array is considered fair if the sum of elements at even indices is equal to the sum of elements at odd indices. Your task is to count how many different indices you can remove so that the resulting array is fair.

• You must remove exactly one element.
• Elements are not reused; after removal, indices shift left.
• Return the number of ways to make the array fair by removing a single element.

Thought Process

At first glance, you might consider removing each element one by one and checking if the resulting array is fair by recalculating the sums at even and odd indices. However, this brute-force approach would require recalculating sums for each removal, leading to a time complexity of O(n²), which is inefficient for larger arrays.

To optimize, we need a way to quickly compute the new sums after removing an element without traversing the entire array each time. The key insight is to use prefix sums, separating the sums for even and odd indices. By maintaining running totals for both sides of the removal point, we can efficiently compute the required sums in constant time for each index.

This approach reduces redundant computation and leverages the predictable shifting of indices after removal.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Calculate total sums:
   • Compute the total sum of elements at even indices (total_even) and at odd indices (total_odd).
2. Iterate through each index:
   • For each index i, simulate removing nums[i].
   • Maintain two running sums: left_even and left_odd, representing the sum of even and odd indices to the left of i.
   • Update total_even or total_odd by subtracting nums[i] (since it's being "removed").
3. Account for index shifting:
   • When nums[i] is removed, elements after i shift left, flipping their parity (even/odd index status).
   • New even sum = left_even + total_odd (since the original odd indices after i become even indices).
   • New odd sum = left_odd + total_even (since the original even indices after i become odd indices).
4. Check for fairness:
   • If the new even and odd sums are equal, increment the result counter.
5. Update left sums:
   • Add nums[i] to left_even or left_odd for the next iteration, depending on the parity of i.
6. Return result:
   • After iterating through all indices, return the count of ways to make the array fair.

This method is efficient because it computes the fairness check in constant time for each index, using only a few variables and a single pass through the array.

Example Walkthrough

Let's use the input nums = [2, 1, 6, 4] as an example.

1. Initial total sums:
   • Even indices (0, 2): 2 + 6 = 8
   • Odd indices (1, 3): 1 + 4 = 5
2. Remove index 0 (value 2):
   • Left sums: left_even = 0, left_odd = 0
   • After removal, total_even = 6, total_odd = 5
   • New even sum = left_even + total_odd = 0 + 5 = 5
   • New odd sum = left_odd + total_even = 0 + 6 = 6
   • Not fair (5 ≠ 6)
3. Remove index 1 (value 1):
   • Update left_even = 2, left_odd = 0
   • After removal, total_even = 6, total_odd = 4
   • New even sum = 2 + 4 = 6
   • New odd sum = 0 + 6 = 6
   • Fair (6 = 6), result += 1
4. Remove index 2 (value 6):
   • Update left_even = 2, left_odd = 1
   • After removal, total_even = 0, total_odd = 4
   • New even sum = 2 + 4 = 6
   • New odd sum = 1 + 0 = 1
   • Not fair (6 ≠ 1)
5. Remove index 3 (value 4):
   • Update left_even = 8, left_odd = 1
   • After removal, total_even = 0, total_odd = 0
   • New even sum = 8 + 0 = 8
   • New odd sum = 1 + 0 = 1
   • Not fair (8 ≠ 1)

The only fair removal is at index 1. The function would return 1.

Time and Space Complexity

• Brute-force approach:
  • For each index, recalculate even and odd sums (O(n) per index), so total time is O(n²).
  • Space: O(1), as only a few variables are needed.
• Optimized prefix sum approach (used here):
  • Single pass to compute totals (O(n)), single pass for the main logic (O(n)), so total time is O(n).
  • Space: O(1), only a handful of variables are used.

The optimized approach is highly efficient and suitable even for large input arrays.

Summary

The key to solving the "Ways to Make a Fair Array" problem efficiently is recognizing how index shifting affects parity after removal. By maintaining running totals for even and odd indices and carefully updating them as elements are "removed," we can check fairness in constant time per index. This approach avoids unnecessary recomputation and leverages prefix sums for a clean and optimal O(n) solution.

The solution is elegant because it transforms a seemingly complex parity-shifting problem into a simple running sum calculation, highlighting the power of prefix sums and careful index management.