Skip to content

2541. Minimum Operations to Make Array Equal II

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. 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

Solutions

Solution 1: Single Pass

We use two variables \(a\) and \(b\) to record the number of times elements in \(\textit{nums1}\) are increased by \(k\) and decreased by \(k\), respectively.

We iterate over both arrays. If the two elements at the current position are equal, we continue. Otherwise, if \(k\) equals \(0\) or the difference between the two elements is not divisible by \(k\), we return \(-1\). Otherwise, we compute \(t = (x - y) / k\). If \(t < 0\), we add \(-t\) to \(a\); otherwise, we add \(t\) to \(b\).

Finally, if \(a\) equals \(b\), we return \(a\); otherwise, we return \(-1\).

The time complexity is \(O(n)\), where \(n\) is the length of the two arrays. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        a = b = 0
        for x, y in zip(nums1, nums2):
            if x == y:
                continue
            if k == 0 or (x - y) % k:
                return -1
            t = (x - y) // k
            if t < 0:
                a += -t
            else:
                b += t
        return a if a == b else -1

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minOperations(nums1 []int, nums2 []int, k int) int64 {
    var a, b int64
    for i, x := range nums1 {
        y := nums2[i]
        if x == y {
            continue
        }
        if k == 0 || (x-y)%k != 0 {
            return -1
        }
        t := (x - y) / k
        if t < 0 {
            a += int64(-t)
        } else {
            b += int64(t)
        }
    }
    if a == b {
        return a
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function minOperations(nums1: number[], nums2: number[], k: number): number {
    let [a, b] = [0, 0];
    for (let i = 0; i < nums1.length; ++i) {
        const [x, y] = [nums1[i], nums2[i]];
        if (x === y) {
            continue;
        }
        if (k === 0 || (x - y) % k !== 0) {
            return -1;
        }
        const t = (x - y) / k;
        if (t < 0) {
            a += -t;
        } else {
            b += t;
        }
    }
    return a === b ? a : -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
impl Solution {
    pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
        let mut a: i64 = 0;
        let mut b: i64 = 0;
        for (&x, &y) in nums1.iter().zip(nums2.iter()) {
            if x == y {
                continue;
            }
            if k == 0 || (x - y) % k != 0 {
                return -1;
            }
            let t = (x - y) / k;
            if t < 0 {
                a += (-t) as i64;
            } else {
                b += t as i64;
            }
        }
        if a == b {
            a
        } else {
            -1
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
long long minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
    long long a = 0, b = 0;
    for (int i = 0; i < nums1Size; ++i) {
        int x = nums1[i], y = nums2[i];
        if (x == y) {
            continue;
        }
        if (k == 0 || (x - y) % k != 0) {
            return -1;
        }
        int t = (x - y) / k;
        if (t < 0) {
            a += -t;
        } else {
            b += t;
        }
    }
    return a == b ? a : -1;
}

Comments