Minimum Operations to Make Array Equal II

This is the most efficient approach, which solves the problem in a single pass through the arrays. It simultaneously checks for impossibility conditions and calculates the required operations by keeping track of the total positive and negative differences needed.

• Handle the edge case where k = 0. If nums1 and nums2 are not equal, return -1. Otherwise, return 0.
• Initialize two long variables: pos_diff_sum = 0 (to track total required increments) and neg_diff_sum = 0 (to track total required decrements).
• Single Pass: Iterate through the arrays from i = 0 to n-1.
  • Calculate the difference diff = (long)nums2[i] - nums1[i].
  • Check if diff is divisible by k. If not, it's impossible, so return -1.
  • If diff > 0, add diff to pos_diff_sum. This represents a deficit in nums1[i] that needs to be filled by increments.
  • If diff < 0, add diff to neg_diff_sum. This represents a surplus in nums1[i] that needs to be removed by decrements.
• After the loop, check if the total deficits balance the total surpluses: pos_diff_sum + neg_diff_sum != 0. If they don't balance, it's impossible to make the arrays equal. Return -1.
• If they do balance, the total number of operations is the total amount of increments needed divided by k. Return pos_diff_sum / k.

This approach is based on the key observation that the total amount of increments required must exactly balance the total amount of decrements. An operation (nums1[i] += k, nums1[j] -= k) essentially "transfers" a value of k from index j to index i.

We can iterate through the arrays once, calculating the difference diff = nums2[i] - nums1[i] at each index. We maintain two running sums:

• pos_diff_sum: The sum of all positive differences. This represents the total value that needs to be added to nums1 across all indices that require an increase.
• neg_diff_sum: The sum of all negative differences. This represents the total value that needs to be subtracted from nums1 across all indices that require a decrease.

During the iteration, we can immediately check if any diff is not divisible by k. After the loop, for a solution to be possible, the total increments must equal the total decrements, meaning pos_diff_sum must be equal to -neg_diff_sum, or pos_diff_sum + neg_diff_sum == 0. If this holds, the number of operations is simply pos_diff_sum / k, as each operation contributes k towards fulfilling the total positive difference.

class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        if (k == 0) {
            for (int i = 0; i < n; i++) {
                if (nums1[i] != nums2[i]) {
                    return -1;
                }
            }
            return 0;
        }

        long pos_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's positive
        long neg_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's negative

        for (int i = 0; i < n; i++) {
            long diff = (long)nums2[i] - nums1[i];

            if (diff % k != 0) {
                return -1;
            }

            if (diff > 0) {
                pos_diff_sum += diff;
            } else {
                neg_diff_sum += diff;
            }
        }

        if (pos_diff_sum + neg_diff_sum != 0) {
            return -1;
        }

        return pos_diff_sum / k;
    }
}