Minimum Operations to Make Array Equal II — LeetCode 2541 Python Solution

The problem

You are given two integer arrays nums1 and nums2 of equal length n and an integer k. You can perform the following operation on nums1: Choose two indexes i and j and increment nums1[i] by k and decrement nums1[j] by k.

Example

Input

nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3

Output

2

Explanation

In 2 operations, we can transform nums1 to nums2.

Python solution

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = x = 0
        for a, b in zip(nums1, nums2):
            if k == 0:
                if a != b:
                    return -1
                continue
            if (a - b) % k:
                return -1
            y = (a - b) // k
            ans += abs(y)
            x += y
        return -1 if x else ans // 2

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2541. Minimum Operations to Make Array Equal II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems