Ways to Make a Fair Array - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,6,4]

› Output: 1

💡 Note: Only removing index 1 makes the array fair. After removing nums[1]=1, we get [2,6,4]. Even indices sum: 2+4=6, Odd indices sum: 6. Since 6=6, it's fair.

Example 2 — Multiple Solutions

$ Input: nums = [1,1,1]

› Output: 3

💡 Note: Removing any element results in [1,1]. Even sum = 1, Odd sum = 1. All three removals work.

Example 3 — No Solution

$ Input: nums = [1,2,3]

› Output: 0

💡 Note: No removal makes the array fair. Remove 1→[2,3] (2≠3), Remove 2→[1,3] (1≠3), Remove 3→[1,2] (1≠2).

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements at even and odd positions

Try Removal

Remove element and check if remaining array is fair

Count Solutions

Count how many removals result in fair arrays

Key Takeaway

🎯 Key Insight: When removing an element, all subsequent elements shift positions, changing the even/odd balance

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that when you remove an element, all elements after it shift positions - odd indices become even and vice versa. The optimal prefix sum approach pre-calculates totals and uses math formulas to determine new sums in O(1) time per removal. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n)	O(1)	Pre-calculate prefix sums to efficiently compute sums after removal
Brute Force Simulation	O(n²)	O(n)	Try removing each element and check if remaining array is fair

Prefix Sum Optimization — Algorithm Steps

Calculate prefix sums for even and odd positions
For each removal index, compute new even/odd sums using prefix sums
Account for position shifts after removal
Check if new sums are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Totals

Pre-compute total even and odd position sums

Track Prefixes

Keep running sums of elements before current position

Efficient Check

Use formula to get new sums after removal in O(1)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize == 1) return 1;
    
    // Calculate total sums for even and odd positions
    int totalEven = 0, totalOdd = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i % 2 == 0) {
            totalEven += nums[i];
        } else {
            totalOdd += nums[i];
        }
    }
    
    int count = 0;
    int leftEven = 0;  // Sum of even positions before current index
    int leftOdd = 0;   // Sum of odd positions before current index
    
    for (int i = 0; i < numsSize; i++) {
        int newEven, newOdd;
        
        if (i % 2 == 0) {  // Removing even positioned element
            newEven = leftEven + (totalOdd - leftOdd);
            newOdd = leftOdd + (totalEven - leftEven - nums[i]);
        } else {  // Removing odd positioned element
            newEven = leftEven + (totalOdd - leftOdd - nums[i]);
            newOdd = leftOdd + (totalEven - leftEven);
        }
        
        if (newEven == newOdd) {
            count++;
        }
        
        // Update prefix sums
        if (i % 2 == 0) {
            leftEven += nums[i];
        } else {
            leftOdd += nums[i];
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to compute prefix sums, then O(1) check for each removal

✓ Linear Growth

Space Complexity

O(1)

Only stores a few variables for prefix sums

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler