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 _theminimum number of operations required to make _nums1 equal tonums2. If it is impossible to make them equal, return -1.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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 <= 10^5
  • 0 <= nums1[i], nums2[j] <= 10^9
  • 0 <= k <= 10^5

Solution

Method 1 – Greedy & Counting

Intuition

The operation allows us to transfer k units from one index to another. For the transformation to be possible, the total sum of differences must be zero, and each difference must be divisible by k. We count how many positive and negative k-steps are needed and match them up.

Approach

  1. For each i, compute diff = nums1[i] - nums2[i].
  2. If k == 0, check if nums1 == nums2; if not, return -1.
  3. If diff % k != 0 for any i, return -1.
  4. Sum up all positive steps (diff > 0) and negative steps (diff < 0), both divided by k.
  5. If total positive steps != total negative steps, return -1.
  6. The answer is total positive steps (or total negative steps).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    long long minOperations(vector<int>& nums1, vector<int>& nums2, int k) {
        if (k == 0) return nums1 == nums2 ? 0 : -1;
        long long pos = 0, neg = 0;
        for (int i = 0; i < nums1.size(); ++i) {
            int d = nums1[i] - nums2[i];
            if (d % k != 0) return -1;
            if (d > 0) pos += d / k;
            else neg -= d / k;
        }
        return pos == neg ? pos : -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func minOperations(nums1 []int, nums2 []int, k int) int64 {
    if k == 0 {
        for i := range nums1 {
            if nums1[i] != nums2[i] {
                return -1
            }
        }
        return 0
    }
    var pos, neg int64
    for i := range nums1 {
        d := nums1[i] - nums2[i]
        if d%k != 0 {
            return -1
        }
        if d > 0 {
            pos += int64(d / k)
        } else {
            neg -= int64(d / k)
        }
    }
    if pos != neg {
        return -1
    }
    return pos
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        if (k == 0) {
            for (int i = 0; i < nums1.length; ++i) {
                if (nums1[i] != nums2[i]) return -1;
            }
            return 0;
        }
        long pos = 0, neg = 0;
        for (int i = 0; i < nums1.length; ++i) {
            int d = nums1[i] - nums2[i];
            if (d % k != 0) return -1;
            if (d > 0) pos += d / k;
            else neg -= d / k;
        }
        return pos == neg ? pos : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minOperations(nums1: IntArray, nums2: IntArray, k: Int): Long {
        if (k == 0) {
            for (i in nums1.indices) {
                if (nums1[i] != nums2[i]) return -1
            }
            return 0
        }
        var pos = 0L
        var neg = 0L
        for (i in nums1.indices) {
            val d = nums1[i] - nums2[i]
            if (d % k != 0) return -1
            if (d > 0) pos += d / k
            else neg -= d / k
        }
        return if (pos == neg) pos else -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minOperations(self, nums1: list[int], nums2: list[int], k: int) -> int:
        if k == 0:
            return 0 if nums1 == nums2 else -1
        pos: int = 0
        neg: int = 0
        for a, b in zip(nums1, nums2):
            d: int = a - b
            if d % k != 0:
                return -1
            if d > 0:
                pos += d // k
            else:
                neg -= d // k
        return pos if pos == neg else -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
        if k == 0 {
            return if nums1 == nums2 { 0 } else { -1 };
        }
        let mut pos: i64 = 0;
        let mut neg: i64 = 0;
        for i in 0..nums1.len() {
            let d = nums1[i] - nums2[i];
            if d % k != 0 {
                return -1;
            }
            if d > 0 {
                pos += (d / k) as i64;
            } else {
                neg -= (d / k) as i64;
            }
        }
        if pos == neg { pos } else { -1 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minOperations(nums1: number[], nums2: number[], k: number): number {
        if (k === 0) return nums1.every((v, i) => v === nums2[i]) ? 0 : -1;
        let pos = 0, neg = 0;
        for (let i = 0; i < nums1.length; ++i) {
            const d = nums1[i] - nums2[i];
            if (d % k !== 0) return -1;
            if (d > 0) pos += d / k;
            else neg -= d / k;
        }
        return pos === neg ? pos : -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the arrays once, computing differences and summing.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.