1067MediumArrayBinary SearchSortingPrefix Sum

Cost of Bringing Every Gauge to Each Target

Tracked in this browser only

Trains the technique from

LeetCode 2602Minimum Operations to Make All Array Elements Equal

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 rail of gauges reads gauges. One turn changes a single gauge by one, up or down.

Each entry of targets asks a separate question, and the rail is never actually changed: how many turns would it take to bring every gauge to that target reading?

Return the answers in the order the questions are asked.

Examples

Example 1

Input: gauges = [1, 2, 3], targets = [2]
Output: [2]

Bringing everything to two costs one turn on the 1, nothing on the 2 and one turn on the 3.

Example 2

Input: gauges = [5], targets = [1, 5, 9]
Output: [4, 0, 4]

A single gauge reading five costs four turns to reach one, nothing to reach five, and four again to reach nine.

Example 3

Input: gauges = [10, 10], targets = [10]
Output: [0]

Both gauges already read the target, so nothing needs turning.

Constraints

1 <= gauges.length <= 10^5
1 <= targets.length <= 10^5
1 <= gauges[i] <= 10^9
1 <= targets[i] <= 10^9

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 min_operations(gauges: list[int], targets: list[int]) -> list[int]:

Java

public List<Long> minOperations(int[] gauges, int[] targets)

The intended approach

Time O(n log n + q log n) for n gauges and q questions.Space O(n) for the sorted gauges and their running totals.

The cost of a target is how far each gauge sits from it added up. Answering each question by walking the whole rail would cost the rail times the questions, so prepare once and answer quickly. Sort the gauges and work out the running totals of the sorted readings. For a target, the gauges below it each contribute the target less their own reading, and the gauges at or above it each contribute their reading less the target. So find by halving how many gauges fall below the target; that count times the target, less their running total, gives the first part, and the rest's running total, less their count times the target, gives the second. That is one halving search and a handful of arithmetic per question, after a single sort.

Pythonentry point: min_operations

def min_operations(gauges, targets):
    from bisect import bisect_left
    order = sorted(gauges)
    n = len(order)
    running = [0] * (n + 1)
    for at in range(n):
        running[at + 1] = running[at] + order[at]
    out = []
    for target in targets:
        cut = bisect_left(order, target)
        below = cut * target - running[cut]
        above = (running[n] - running[cut]) - (n - cut) * target
        out.append(below + above)
    return out

The obvious version

Answer each question by walking the whole rail, adding up how far every gauge sits from that target. Costs the rail times the questions rather than a sort and a halving search apiece.

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_min_operations(gauges, targets):
    out = []
    for target in targets:
        total = 0
        for value in gauges:
            total += value - target if value > target else target - value
        out.append(total)
    return out

How this problem was checked

Reference solution executed against 17 test cases — 17 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