Transfers in Steps of Two

Hard

You get two arrays of positive integers of the same length, values and goal. In one operation you choose two **different** indices i and j, add 2 to values[i] and subtract 2 from values[j]. The aim is for values and goal to match as collections: every number occurs the same number of times in both, and the order does not matter. Return the smallest number of operations. The aim is guaranteed to be reachable.

Example 1

values=[7, 4, 10], goal=[8, 5, 8] → 2

Move 2 from element 0 to element 1: [5, 6, 10], then from element 2 to element 1: [5, 8, 8], the same collection as goal.

Example 2

values=[6, 3, 1], goal=[1, 3, 6] → 0

Order does not matter: the collections already match.

Constraints

1 ≤ len(values) = len(goal) ≤ 10⁵
1 ≤ values[i], goal[i] ≤ 10⁶
values can be turned into the collection goal

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Growing Capital Project by Project Hard Distinct Word Shorthands Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Two Marks in Every Range Hard

Input

values=[7, 4, 10], goal=[8, 5, 8]

Expected

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