Ways to Make a Fair Array

Call an array fair if the sum of the values at even indices equals the sum of the values at odd indices (indices start at 0).

You're given an integer array nums. You may delete exactly one element. After the deletion, the elements to its right shift left by one, so their indices change.

Return how many indices i there are such that deleting nums[i] leaves a fair array. An empty array counts as fair, since both sums are 0.

Deleting nums[i] does two different things. Elements before i keep their indices, so their even and odd sums are unchanged. Elements after i all shift left by one, so every even index becomes odd and every odd index becomes even.

That means the new even sum is (even sum before i) + (odd sum after i), and the new odd sum is (odd sum before i) + (even sum after i). If you know the four partial sums at every position, each deletion is a constant-time check. Keep running "before" sums as you walk, and get "after" sums by subtracting from the totals.

def ways_to_make_fair(nums: list[int]) -> int:
    even_total = sum(nums[0::2])
    odd_total = sum(nums[1::2])
    even_left = odd_left = 0
    count = 0
    for i, x in enumerate(nums):
        if i % 2 == 0:
            even_total -= x
        else:
            odd_total -= x
        # Everything right of i flips parity after the deletion.
        if even_left + odd_total == odd_left + even_total:
            count += 1
        if i % 2 == 0:
            even_left += x
        else:
            odd_left += x
    return count

function waysToMakeFair(nums) {
  let evenTotal = 0;
  let oddTotal = 0;
  nums.forEach((x, i) => {
    if (i % 2 === 0) evenTotal += x;
    else oddTotal += x;
  });
  let evenLeft = 0;
  let oddLeft = 0;
  let count = 0;
  nums.forEach((x, i) => {
    if (i % 2 === 0) evenTotal -= x;
    else oddTotal -= x;
    // Everything right of i flips parity after the deletion.
    if (evenLeft + oddTotal === oddLeft + evenTotal) count++;
    if (i % 2 === 0) evenLeft += x;
    else oddLeft += x;
  });
  return count;
}

The whole problem hinges on one observation, so say it before coding: "deletion keeps the left part's parities and flips the right part's." Then write the balance formula with the four sums and the code follows.

Interviewers like to see you check the formula on a tiny case like [2, 1, 6, 4] deleting index 1, and to hear you explain why the O(1) space version works: the "after" sums are just totals minus what you've already passed.