1664. Ways to Make a Fair Array #

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

Problem Summary #

You are given an integer array nums . You need to choose exactly one index (0-indexed) and delete the corresponding element. Note that the indices of the remaining elements may change because of the deletion.

For example, if nums = [6,1,7,4,1] , then:

Choosing to delete index 1 leaves the array nums = [6,7,4,1] .
Choosing to delete index 2 leaves the array nums = [6,1,4,1] .
Choosing to delete index 4 leaves the array nums = [6,1,7,4] .

If an array satisfies that the sum of the elements at odd indices equals the sum of the elements at even indices, then the array is a fair array. Return the number of ways such that, after the deletion operation, the remaining array nums is a fair array.

Solution Approach #

Given an array nums, output the number of ways to make the entire array fair after deleting exactly one element. A fair array is defined as one where the total sum of elements at odd indices equals the total sum of elements at even indices.
A brute-force solution for this problem will time out. The reason is that after deleting each element, recomputing the total sums at odd and even positions is time-consuming. We should use the previously computed cumulative sums to derive the situation after the current deletion. After this modification, it will not time out. Specifically, if the deleted element is at an odd position, the prefix sums before this index remain unchanged, while the part after it changes. After deleting the element, the original sum of even positions in the suffix becomes the sum of odd positions, and the original sum of odd positions becomes the sum of even positions. The total sum of the half after the deleted element can be computed with prefix sums. Subtracting the prefix sum of the deleted element from the odd-position total gives the suffix sum after the deleted element. In this way, we can get the odd-position sum and even-position sum after the deleted element. Note that this suffix sum includes the deleted element. Therefore, in the end, we need to check whether the deleted element is at an odd or even position. If it is at an odd position, subtract this deleted element again from the computed even sum; if it is at an even position, subtract this deleted element again from the computed odd sum. See Solution 2 in the code.
There is another more concise way to write this problem, which is Solution 1. Through the thinking in Solution 2, we can see that the operations after each transformation can be abstracted into three steps: subtract a number, check whether the two sums are equal, then add a number. It is just that in Solution 2, parity is checked in all three steps. If we do not check parity, the code can be written in the form of Solution 1. Why can we ignore parity? Because after deleting one element each time, for the next deletion, odd and even positions are reversed; the previous odd sum becomes the even sum next time. Once you understand this, you can write the code in the style of Solution 1.

Code #

// Solution 1: ultra-concise implementation
func waysToMakeFair(nums []int) int {
	sum, res := [2]int{}, 0
	for i := 0; i < len(nums); i++ {
		sum[i%2] += nums[i]
	}
	for i := 0; i < len(nums); i++ {
		sum[i%2] -= nums[i]
		if sum[i%2] == sum[1-(i%2)] {
			res++
		}
		sum[1-(i%2)] += nums[i]
	}
	return res
}

// Solution 2: prefix sums and suffix sums
func waysToMakeFair1(nums []int) int {
	evenPrefix, oddPrefix, evenSuffix, oddSuffix, res := 0, 0, 0, 0, 0
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			evenSuffix += nums[i]
		} else {
			oddSuffix += nums[i]
		}
	}
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			evenSuffix -= nums[i]
		} else {
			oddSuffix -= nums[i]
		}
		if (evenPrefix + oddSuffix) == (oddPrefix + evenSuffix) {
			res++
		}
		if i%2 == 0 {
			evenPrefix += nums[i]
		} else {
			oddPrefix += nums[i]
		}
	}
	return res
}