LeetCode 2541. Minimum Operations to Make Array Equal II

2541. Minimum Operations to Make Array Equal II

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

效能

• Time complexity: O(2n)
• Space complexity: O(1)
• Runtime: 256 ms
• Memory: 53.7 MB

題解

Biweekly Contest 96，Medium。

最終的目的是要想辦法讓 nums1 變得和 nums2 一樣，辦不到就回傳 -1，可以就回傳執行的次數。執行的方法是：取出 nums1 的兩個數字，其中一個 +k，另外一個 -k。

解法

先處理 k = 0 的情況。假設 k 是 0，不論怎麼 +k 或 -k，原本的數字都不會變，也就是 nums1 原本的值，就必須等於 nums2，否則就無法把 nums1 變成 nums2，回傳 -1。

if (k == 0) 
{ 
    for (var index = 0; index < nums1.Length; index++) 
    { 
        if (nums1[index] != nums2[index]) return -1; 
    } 
    return 0; 
}

如果 k > 0，就要考慮有進行操作的情況。因為題目規定必須同時一加一減，也就代表加的次數和減的次數必須一致，才算是操作一次，否則就算是不成功，回傳 -1。

有了回傳結論後，接下來要處理計算加減次數的部分。假設 nums1 有個數字是 8，nums2 則是 [1, 3, 7, 1]，k = 3，這個 8 無論怎麼 +- k，都不會變成 [1, 3, 7] 的一種，因為 8 和這幾個數字都沒有辦法剛好被 3 整除。所以，只要 nums1 中，有一個數字和 nums2 的差沒有辦法被 k 整除，就沒有辦法透過 +- k 的操作，來讓它變成 nums2，直接回傳 -1。

寫成程式碼的話，會像是這樣子：

public long MinOperations(int[] nums1, int[] nums2, int k) { 
    // 先處理 k = 0 
    if (k == 0) 
    { 
        for (var index = 0; index < nums1.Length; index++) 
        { 
            if (nums1[index] != nums2[index]) return -1; 
        } 
        return 0; 
    } 
 
    // 分別記錄加減次數 
    long plusCount = 0; 
    long reduceCount = 0; 
 
    for (var index = 0; index < nums1.Length; index ++) 
    { 
        // 判斷兩者的差是否可以被 k 整除 
        var diff = nums1[index] - nums2[index]; 
        if (diff % k != 0) return -1; 
 
        // 找出透過加減，需要處理幾次 
        long count = Math.Abs(diff) / k; 
 
        // 如果 diff == 0，就是需要處理 0 次 
        // 因此等於的情況不管放大於還是小於都不影響 
        if (nums1[index] <= nums2[index]) 
        { 
            plusCount += count; 
        } 
        else 
        { 
            reduceCount += count; 
        } 
    } 
 
    // 如果次數不相等代表沒辦法同時進行 
    if (reduceCount != plusCount) return -1; 
    return plusCount; 
}

參考資料

• 2541. Minimum Operations to Make Array Equal II
• Ranking of Biweekly Contest 96：xuxiaohu