Ways to Make a Fair Array
Problem
You are given an integer array nums and must delete exactly one element. After the deletion the remaining values close ranks and are re-indexed from 0. The result is called fair when the sum of the values sitting at even indices equals the sum of the values sitting at odd indices. Count how many choices of the deleted index leave a fair array.
nums = [2, 1, 6, 4]1def ways_to_make_fair(nums):
right_even = sum(nums[0::2])
right_odd = sum(nums[1::2])
left_even = left_odd = 0
count = 0
for i, v in enumerate(nums):
if i % 2 == 0:
right_even -= v
else:
right_odd -= v
if left_even + right_odd == left_odd + right_even:
count += 1
if i % 2 == 0:
left_even += v
else:
left_odd += v
return countfunction waysToMakeFair(nums) {
let rightEven = 0, rightOdd = 0;
for (let i = 0; i < nums.length; i++) {
if (i % 2 === 0) rightEven += nums[i];
else rightOdd += nums[i];
}
let leftEven = 0, leftOdd = 0, count = 0;
for (let i = 0; i < nums.length; i++) {
if (i % 2 === 0) rightEven -= nums[i];
else rightOdd -= nums[i];
if (leftEven + rightOdd === leftOdd + rightEven) count++;
if (i % 2 === 0) leftEven += nums[i];
else leftOdd += nums[i];
}
return count;
}int waysToMakeFair(int[] nums) {
int rightEven = 0, rightOdd = 0;
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) rightEven += nums[i];
else rightOdd += nums[i];
}
int leftEven = 0, leftOdd = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) rightEven -= nums[i];
else rightOdd -= nums[i];
if (leftEven + rightOdd == leftOdd + rightEven) count++;
if (i % 2 == 0) leftEven += nums[i];
else leftOdd += nums[i];
}
return count;
}int waysToMakeFair(vector<int>& nums) {
int rightEven = 0, rightOdd = 0;
for (int i = 0; i < (int)nums.size(); i++) {
if (i % 2 == 0) rightEven += nums[i];
else rightOdd += nums[i];
}
int leftEven = 0, leftOdd = 0, count = 0;
for (int i = 0; i < (int)nums.size(); i++) {
if (i % 2 == 0) rightEven -= nums[i];
else rightOdd -= nums[i];
if (leftEven + rightOdd == leftOdd + rightEven) count++;
if (i % 2 == 0) leftEven += nums[i];
else leftOdd += nums[i];
}
return count;
}Explanation
Re-summing the array after every candidate deletion costs O(n²). The trick that makes this O(n) is a parity observation: when index i is deleted, everything before i keeps its index, but everything after i shifts left by one — so every suffix element's index parity flips. A value that sat at an odd index suddenly sits at an even index, and vice versa.
That means the array obtained by deleting i has even-index sum leftEven + rightOdd and odd-index sum leftOdd + rightEven, where the left totals cover indices strictly before i (parity unchanged) and the right totals cover indices strictly after i (parity swapped). The deletion is fair exactly when those two combined sums are equal.
We can evaluate all n deletions in a single sweep. Start with rightEven and rightOdd holding the parity totals of the whole array and both left counters at zero. At each index, first pull nums[i] out of its right-side bucket (it is being deleted, so it belongs to neither side), do the O(1) fairness check, then push nums[i] into its left-side bucket before moving on. Each element changes sides exactly once.
Walking the default example nums = [2, 1, 6, 4]: the totals are even = 2 + 6 = 8 and odd = 1 + 4 = 5. Deleting index 0 gives 0 + 5 = 5 versus 0 + 6 = 6 — not fair. Deleting index 1 gives 2 + 4 = 6 versus 0 + 6 = 6 — fair. Deleting index 2 gives 2 + 4 = 6 versus 1 + 0 = 1, and deleting index 3 gives 8 + 0 = 8 versus 1 + 0 = 1 — neither is fair. The answer is 1.
The first pass computes the totals and the second pass does constant work per index, so the time is O(n). Only four running counters are kept, so the extra space is O(1).