Problem Explanation

Let's say you're provided an array of integers - nums. You can choose exactly one index (0-indexed) and remove the element from the array. Keep in mind that the index of the elements may change after the removal. For instance, if we have nums = [6,1,7,4,1]. Here, if we remove index 1, we get nums = [6,7,4,1]. Or, if we decide to remove index 2, we get nums = [6,1,4,1].

We refer to an array as "fair" if the sum of all odd-indexed values equals the sum of all even-indexed values. You have to return the number of indices that you could choose such that after the removal, nums ends up being a "fair" array.

For example, let's say nums is [2,1,6,4]. The answer here would be 1 since there is 1 index (index 1) that you can remove to make the array "fair".

Solution Approach

The best option to tackle this problem will be to use Dynamic Programming with Prefix Sums. We will calculate prefix sums for even and odd indices to divide the array into two parts where the elements on the left are the discarded elements and the ones on the right are the kept elements after removing an element with an index i.

For the left part, we calculate with even[i] and odd[i], while for the right part we subtract elements on the left from total to fetch the sum.

The algorithm iterates over the array to count the indices where the sum of the even index and the sum of the odd index are the same after removing it.

Let's break down the code now:

Python Solution

1
2python
3class Solution(object):
4    def waysToMakeFair(self, nums):
5        N = len(nums)
6        even, odd = [0]*(N+1), [0]*(N+1)
7        for i in range(N):
8            if i%2==0: even[i+1] = even[i] + nums[i]
9            else: odd[i+1] = odd[i] + nums[i]
10        count = 0
11        for i in range(N):
12            count += (even[i] + odd[-1] - odd[i+1]) == (odd[i] + even[-1] - even[i+1])
13        return count

Java Solution

1
2java
3public class Solution {
4    public int waysToMakeFair(int[] nums) {
5        int n = nums.length;
6        int evenSum[] = new int[n+1];
7        int oddSum[] = new int[n+1];
8        int count = 0;
9        for (int i = 1; i <= n; i++) {
10            if (i % 2 == 0){
11                evenSum[i] = evenSum[i - 1] + nums[i - 1];
12                oddSum[i] = oddSum[i - 1];
13            } else {
14                oddSum[i] = oddSum[i - 1] + nums[i - 1];
15                evenSum[i] = evenSum[i - 1];
16            }
17        }
18        for (int i = 0; i < n; i++) {
19            if (evenSum[i] + (oddSum[n] - oddSum[i + 1]) == (oddSum[i] + (evenSum[n] - evenSum[i + 1]))){
20                count++;
21            }
22        }
23        return count;
24    }
25}

JavaScript Solution

1
2javascript
3class Solution {
4    waysToMakeFair(nums) {
5        let n = nums.length, evenSum = new Array(n+1).fill(0), oddSum = new Array(n+1).fill(0), count = 0;
6        for (let i = 1; i <= n; i++) {
7            oddSum[i] = oddSum[i - 1];
8            evenSum[i] = evenSum[i - 1];
9            if (i % 2 == 0) evenSum[i] += nums[i - 1];
10            else oddSum[i] += nums[i - 1];
11        }
12        for (let i = 0; i < n; i++) {
13            let evenSumTemp = evenSum[i] + (oddSum[n] - oddSum[i + 1]); 
14            let oddSumTemp = oddSum[i] + (evenSum[n] - evenSum[i + 1]);
15            if (evenSumTemp == oddSumTemp) count++;
16        }
17        return count;
18    }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int waysToMakeFair(vector<int>& nums) {
6        int even = 0, odds = 0;
7        for(int i = 0; i < nums.size(); ++i){
8            if(i & 1) odds+= nums[i];
9            else even+= nums[i];
10        }
11        int ans = 0, curr_even = 0, curr_odds = 0;
12        for(int i = 0; i < nums.size(); ++i){
13            if(i & 1) odds -= nums[i];
14            else even -= nums[i];
15            if(curr_even + odds == curr_odds + even) ++ans;
16            if(i & 1) curr_odds += nums[i];
17            else curr_even += nums[i];
18        }
19        return ans;
20    }
21};

C# Solution

1
2cs
3public class Solution {
4    public int WaysToMakeFair(int[] nums) {
5        int n = nums.Length;
6        int[] sum1 = new int[n+1];
7        int[] sum2 = new int[n+1];
8        int cnt = 0;
9        for(int i = 1; i <= n; i++) {
10            if(i % 2 != 0) {
11                sum1[i] = sum1[i - 1] + nums[i - 1];
12                sum2[i] = sum2[i - 1];
13            } else {
14                sum2[i] = sum2[i - 1] + nums[i - 1];
15                sum1[i] = sum1[i - 1];
16            }
17        }
18        for(int i = 1; i <= n; i++) {
19            if(sum1[i - 1] + sum2[n] - sum2[i] == sum2[i - 1] + sum1[n] - sum1[i]) cnt++;
20        }
21        return cnt;
22    }
23}

Wrapping it up! We initialized even and odd array with n+1 zeros. Then, for every i in the length of given array, we iteratively add the current number to even sum or odd sum depending on if this index is even or odd. Then we use another loop to check and count the fair number by comparing the left even summed with right odd summed and left odd summed with right even summed. Finally, return the accumulated counts.

Swift Solution

1
2swift
3class Solution {
4    func waysToMakeFair(_ nums: [Int]) -> Int {
5        let n = nums.count
6        var evenSum = Array(repeating: 0, count: n + 1)
7        var oddSum = Array(repeating: 0, count: n + 1)
8        var count = 0
9        for i in 0..<n {
10            if i % 2 == 0 {
11                evenSum[i + 1] = evenSum[i] + nums[i]
12                oddSum[i + 1] = oddSum[i]
13            } else {
14                oddSum[i + 1] = oddSum[i] + nums[i]
15                evenSum[i + 1] = evenSum[i]
16            }
17        }
18        for i in 0..<n {
19            let leftEvenSum = evenSum[i]
20            let rightOddSum = oddSum[n] - oddSum[i + 1]
21            let leftOddSum = oddSum[i]
22            let rightEvenSum = evenSum[n] - evenSum[i + 1]
23            if (leftEvenSum + rightOddSum) == (leftOddSum + rightEvenSum) {
24                count += 1
25            }
26        }
27        return count
28    }
29}

In the Swift solution, we first defined two arrays, evenSum and oddSum, and initialize them with 0s. We then loop through the elements in the input array nums. If an index is even, we add the corresponding value to evenSum and keep the oddSum unchanged, and vice versa. After that, we examine every index and check if the sums of the left even indices and right odd indices equal the sums of the left odd indices and right even indices. If they do, we increment the count. Eventually, we return the count that indicates the number of indices we can remove to make the array fair.

Go Solution

1
2go
3func waysToMakeFair(nums []int) int {
4    n := len(nums)
5    evenSum, oddSum := make([]int, n+1), make([]int, n+1)
6    count := 0
7    for i := 1; i <= n; i++ {
8        if i % 2 == 0 {
9            evenSum[i] = evenSum[i - 1] + nums[i - 1]
10            oddSum[i] = oddSum[i - 1]
11        } else {
12            oddSum[i] = oddSum[i - 1] + nums[i - 1]
13            evenSum[i] = evenSum[i - 1]
14        }
15    }
16    for i := 0; i < n; i++ {
17        leftEvenSum := evenSum[i]
18        rightOddSum := oddSum[n] - oddSum[i + 1]
19        leftOddSum := oddSum[i]
20        rightEvenSum := evenSum[n] - evenSum[i + 1]
21        if leftEvenSum + rightOddSum == leftOddSum + rightEvenSum {
22            count++
23        }
24    }
25    return count
26}

The Go solution follows the same approach. But instead of using [Int] for array declaration, we use make(). And instead of count += 1, we use count++ as syntax is different in Go. With this approach, we are able to design the solutions in multiple languages adhering to the same underlying logic, with differences only in language-specific syntax.