{x}
blog image

Ways to Make a Fair Array

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

1664. Ways to Make a Fair Array

Problem Description

Given an integer array nums, you can choose exactly one index (0-indexed) and remove the element. An array is considered fair if the sum of its odd-indexed values equals the sum of its even-indexed values. Return the number of indices that you could choose such that after the removal, nums is fair.

Solution: Enumeration with Prefix Sum Optimization

This problem can be efficiently solved using a single pass through the array with prefix sum optimization. The naive approach would involve iterating through each possible removal, then calculating even/odd sums for each resulting array, leading to O(n^2) complexity. The optimized approach reduces this to O(n).

Algorithm:

  1. Precompute Total Even/Odd Sums: First, calculate the total sum of even-indexed elements (s1) and the total sum of odd-indexed elements (s2) in the original nums array.

  2. Iterate and Update: Iterate through nums. For each element v at index i:

    • If i is even: Removing v shifts all subsequent odd indices to even and vice versa. Therefore, we check if t2 + (s1 - t1 - v) == t1 + (s2 - t2) (where t1 and t2 track the sums of even and odd indices up to the current element). If true, increment the count of fair arrays.
    • If i is odd: Similarly, check if t2 + (s1 - t1) == t1 + (s2 - t2 - v). If true, increment the count.
    • Update t1 and t2 to include the current v.

  3. Return Count: After iterating through all elements, return the final count of fair arrays.

Code Implementation

The following code implements the optimized solution in several programming languages:

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

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;
    }
}

C++:

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;
    }
};

Go:

func waysToMakeFair(nums []int) int {
    s1, s2 := 0, 0
    for i, v := range nums {
        if i%2 == 0 {
            s1 += v
        } else {
            s2 += v
        }
    }
    t1, t2, ans := 0, 0, 0
    for i, v := range nums {
        if i%2 == 0 && t2+s1-t1-v == t1+s2-t2 {
            ans++
        }
        if i%2 == 1 && t2+s1-t1 == t1+s2-t2-v {
            ans++
        }
        if i%2 == 0 {
            t1 += v
        } else {
            t2 += v
        }
    }
    return ans
}

JavaScript:

var waysToMakeFair = function(nums) {
    let s1 = 0, s2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) s1 += nums[i];
        else s2 += nums[i];
    }
    let t1 = 0, t2 = 0, ans = 0;
    for (let i = 0; i < nums.length; i++) {
        let v = nums[i];
        if (i % 2 === 0 && t2 + s1 - t1 - v === t1 + s2 - t2) ans++;
        if (i % 2 === 1 && t2 + s1 - t1 === t1 + s2 - t2 - v) ans++;
        if (i % 2 === 0) t1 += v;
        else t2 += v;
    }
    return ans;
};

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array only once.
  • Space Complexity: O(1). We use only a constant amount of extra space to store variables.