# Minimum Operations to Make Array Equal II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-array-equal-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-equal-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## 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`. In other words, `nums1[i] = nums1[i] + k` and `nums1[j] = nums1[j] - k`.

`nums1` is said to be **equal** to `nums2` if for all indices `i` such that `0 <= i < n`, `nums1[i] == nums2[i]`.

Return _the **minimum** number of operations required to make_ `nums1` _equal to_ `nums2`. If it is impossible to make them equal, return `-1`.

**Example 1:**

**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.
1st operation: i = 2, j = 0. After applying the operation, nums1 = [1,3,4,4].
2nd operation: i = 2, j = 3. After applying the operation, nums1 = [1,3,7,1].
One can prove that it is impossible to make arrays equal in fewer operations.

**Example 2:**

**Input:** nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
**Output:** -1
**Explanation:** It can be proved that it is impossible to make the two arrays equal.

**Constraints:**

* `n == nums1.length == nums2.length`
* `2 <= n <= 105`
* `0 <= nums1[i], nums2[j] <= 109`
* `0 <= k <= 105`

# Approaches
## Two-Pass Iteration
This approach involves iterating through the arrays twice. The first pass validates if a solution is possible by checking two conditions: the element-wise differences must be divisible by `k`, and the total sum of both arrays must be equal. The second pass calculates the total number of required operations.
**Time:** O(N), where N is the length of the arrays. We perform two separate linear scans of the arrays. · **Space:** O(1), as we only use a few variables to store sums and the operation count, regardless of the input size.
**Pros:** Conceptually simple and easy to understand.; Separates the validation logic from the calculation logic, which can improve readability.
**Cons:** Less efficient as it requires iterating through the input arrays twice, performing more operations than necessary.
### Explanation
The core idea is to first ensure that a transformation is possible before calculating the minimum operations. This separation of concerns can make the logic easier to follow.

### Impossibility Conditions:
1.  **`k = 0`**: If `k` is 0, the operation `nums1[i] += 0` and `nums1[j] -= 0` does not change the array. Therefore, `nums1` can only be made equal to `nums2` if they are already identical. If `nums1[i] != nums2[i]` for any `i`, it's impossible.
2.  **Divisibility**: For `k > 0`, each change to an element `nums1[i]` is a multiple of `k`. Therefore, the difference `nums2[i] - nums1[i]` must be divisible by `k` for all `i`. If not, it's impossible to match `nums1[i]` to `nums2[i]`.
3.  **Sum Equality**: Each operation increases one element by `k` and decreases another by `k`, leaving the total sum of `nums1` unchanged. Thus, a necessary condition is that the sum of elements in `nums1` must equal the sum of elements in `nums2`.

### Calculation:
If all conditions for possibility are met, we can calculate the operations. The total number of operations is determined by the total amount of increments needed. Since the total increments must balance the total decrements (due to sum equality), we only need to count one side. We can sum up all the required `+k` increments and that gives us the answer.

```java
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 sum1 = 0;
        long sum2 = 0;

        // First Pass: Check for impossibility
        for (int i = 0; i < n; i++) {
            if (Math.abs((long)nums1[i] - nums2[i]) % k != 0) {
                return -1;
            }
            sum1 += nums1[i];
            sum2 += nums2[i];
        }

        if (sum1 != sum2) {
            return -1;
        }

        // Second Pass: Calculate operations
        long operations = 0;
        for (int i = 0; i < n; i++) {
            if (nums1[i] < nums2[i]) {
                operations += ((long)nums2[i] - nums1[i]) / k;
            }
        }

        return operations;
    }
}
```
### Algorithm
- Handle the edge case where `k = 0`. If `nums1` and `nums2` are not equal, return -1. Otherwise, return 0.
- **First Pass**: Iterate through the arrays to check for impossibility.
  - Initialize `long` variables `sum1 = 0` and `sum2 = 0`.
  - For each index `i` from `0` to `n-1`:
    - Add `nums1[i]` to `sum1` and `nums2[i]` to `sum2`.
    - Check if the absolute difference `|nums1[i] - nums2[i]|` is not divisible by `k`. If it's not, a solution is impossible, so return -1.
- After the first pass, check if `sum1` is not equal to `sum2`. If the total sums differ, it's impossible to make the arrays equal, so return -1.
- **Second Pass**: If all checks have passed, a solution is guaranteed to exist. Iterate through the arrays again to count the operations.
  - Initialize a `long` counter `operations = 0`.
  - For each index `i`, if `nums1[i] < nums2[i]`, it means `nums1[i]` needs to be incremented. The number of increments of `k` needed is `(nums2[i] - nums1[i]) / k`. Add this value to `operations`.
- Return the final `operations` count.

## Single-Pass Optimal Approach
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.
**Time:** O(N), where N is the length of the arrays. We iterate through the arrays only once. · **Space:** O(1), as we only use a constant amount of extra space for our tracking variables.
**Pros:** Highly efficient, solving the problem in a single pass.; Combines validation and calculation into one loop, reducing redundant work and improving performance.
**Cons:** The logic might be slightly less straightforward to grasp initially compared to the two-pass method as it combines checks and calculations.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution {
public
  long minOperations(int[] nums1, int[] nums2, int k) {
    long ans = 0, x = 0;
    for (int i = 0; i < nums1.length; ++i) {
      int a = nums1[i], b = nums2[i];
      if (k == 0) {
        if (a != b) {
          return -1;
        }
        continue;
      }
      if ((a - b) % k != 0) {
        return -1;
      }
      int y = (a - b) / k;
      ans += Math.abs(y);
      x += y;
    }
    return x == 0 ? ans / 2 : -1;
  }
}

```

### CPP

```cpp
class Solution { public: long long minOperations ( vector < int >& nums1 , vector < int >& nums2 , int k ) { long long ans = 0 , x = 0 ; for ( int i = 0 ; i < nums1 . size (); ++ i ) { int a = nums1 [ i ], b = nums2 [ i ]; if ( k == 0 ) { if ( a != b ) { return - 1 ; } continue ; } if (( a - b ) % k != 0 ) { return - 1 ; } int y = ( a - b ) / k ; ans += abs ( y ); x += y ; } return x == 0 ? ans / 2 : - 1 ; } };
```

### Python

```python
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
```