1084MediumArrayPrefix Sum

Which Single Removal Balances the Halves

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A strip of readings reads readings. Removing exactly one reading closes the gap behind it, so everything after it shifts one place along.

A strip is balanced when the readings at even positions add up to the same as the readings at odd positions, counting positions from zero.

Return how many single removals leave the strip balanced.

Examples

Example 1

Input: readings = [1]
Output: 1

Removing the only reading leaves nothing at all, so both totals are nothing and the strip is balanced.

Example 2

Input: readings = [5, 5]
Output: 0

Either removal leaves one reading at an even position, so the even total is five against nothing.

Example 3

Input: readings = [1, 2, 1, 2]
Output: 1

Removing the first reading leaves 2, 1, 2 with an even total of four against an odd total of one, and so on for the others; only one of the four removals balances.

Constraints

1 <= readings.length <= 10^5
1 <= readings[i] <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def ways_to_make_fair(readings: list[int]) -> int:

Java

public int waysToMakeFair(int[] readings)

The intended approach

Time O(n) over the strip's length.Space O(1).

Removing a reading leaves everything before it where it was and shifts everything after it one place along, which swaps the even and odd roles of the whole tail. So after removing the reading at some place, the even total is the even total of the part before it plus the odd total of the part after it, and the odd total is the other pairing. That means four running totals settle every removal at once: the even and odd totals of the part already passed, and the even and odd totals of the part still to come. Start the trailing pair holding the whole strip, then walk the strip taking each reading out of the trailing pair, testing the balance, and adding it into the leading pair. Testing before adding the reading in is what leaves it out of both parts, which is exactly what removing it means. One pass to set the totals up and one to walk.

Pythonentry point: ways_to_make_fair

def ways_to_make_fair(readings):
    n = len(readings)
    right_even = 0
    right_odd = 0
    for at in range(n):
        if at % 2 == 0:
            right_even += readings[at]
        else:
            right_odd += readings[at]
    left_even = 0
    left_odd = 0
    count = 0
    for at in range(n):
        if at % 2 == 0:
            right_even -= readings[at]
        else:
            right_odd -= readings[at]
        if left_even + right_odd == left_odd + right_even:
            count += 1
        if at % 2 == 0:
            left_even += readings[at]
        else:
            left_odd += readings[at]
    return count

The obvious version

Build the strip without each reading in turn, add up its even and odd positions from scratch, and count the removals that leave the two totals equal. Costs the strip's length squared rather than four running totals.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_ways_to_make_fair(readings):
    n = len(readings)
    count = 0
    for gone in range(n):
        left = readings[:gone] + readings[gone + 1:]
        even = 0
        odd = 0
        for at in range(len(left)):
            if at % 2 == 0:
                even += left[at]
            else:
                odd += left[at]
        if even == odd:
            count += 1
    return count

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in