Shift Cost for Each Target

Medium

You get an array of positive integers values and a list of targets targets. One move raises or lowers any single number in values by 1. For each target targets[i], find how many moves it takes to make every number in values equal to targets[i]. Each target is handled on its own, starting from the original array. Return the answers as a list in the same order.

Example 1

values=[4, 1, 7], targets=[4, 2] → [6, 8]

To 4: 0 + 3 + 3 = 6. To 2: 2 + 1 + 5 = 8.

Example 2

values=[10], targets=[1, 10, 15] → [9, 0, 5]

The single value moves by 9, 0 and 5.

Constraints

1 ≤ len(values), len(targets) ≤ 10⁵
1 ≤ values[i], targets[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Prefix Sum Sorting

Similar problems

Even Out With Increments Medium Rug Over Painted Stretches Medium Climbing Gym Points Medium Nudge Values to Agree Medium Richest Row of Houses Medium

Input

values=[4, 1, 7], targets=[4, 2]

Expected

[6, 8]

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.