Minimum Operations to Make Array Equal II

Problem Description

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. Return the minimum number of operations required to make nums1 equal to nums2. If it is impossible to make them equal, return -1.

Key Insights

• The operation allows us to adjust the values of nums1 but keeps the sum of the array constant.
• The difference between nums1 and nums2 needs to be adjusted to zero using the allowed operations.
• The total surplus and deficit in nums1 must be divisible by k for it to be possible to make the arrays equal.
• Each operation can change two elements, so the number of operations required is determined by the total adjustments needed divided by k.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can:

1. Calculate the differences between nums1 and nums2 for each index.
2. Sum up the positive differences (surplus) and negative differences (deficit).
3. Check if the total surplus is equal to the total deficit and both are divisible by k. If not, return -1.
4. The number of operations needed is the total surplus divided by k.

Code Solutions