2449. Minimum Number of Operations to Make Arrays Similar
Description
You are given two positive integer arrays nums
and target
, of the same length.
In one operation, you can choose any two distinct indices i
and j
where 0 <= i, j < nums.length
and:
- set
nums[i] = nums[i] + 2
and - set
nums[j] = nums[j] - 2
.
Two arrays are considered to be similar if the frequency of each element is the same.
Return the minimum number of operations required to make nums
similar to target
. The test cases are generated such that nums
can always be similar to target
.
Example 1:
Input: nums = [8,12,6], target = [2,14,10] Output: 2 Explanation: It is possible to make nums similar to target in two operations: - Choose i = 0 and j = 2, nums = [10,12,4]. - Choose i = 1 and j = 2, nums = [10,14,2]. It can be shown that 2 is the minimum number of operations needed.
Example 2:
Input: nums = [1,2,5], target = [4,1,3] Output: 1 Explanation: We can make nums similar to target in one operation: - Choose i = 1 and j = 2, nums = [1,4,3].
Example 3:
Input: nums = [1,1,1,1,1], target = [1,1,1,1,1] Output: 0 Explanation: The array nums is already similiar to target.
Constraints:
n == nums.length == target.length
1 <= n <= 105
1 <= nums[i], target[i] <= 106
- It is possible to make
nums
similar totarget
.
Solutions
Solution 1: Odd-Even Classification + Sorting
Notice that, because each operation will only increase or decrease the value of an element by $2$, the parity of the element will not change.
Therefore, we can divide the arrays $nums$ and $target$ into two groups according to their parity, denoted as $a_1$ and $a_2$, and $b_1$ and $b_2$ respectively.
Then, we just need to pair the elements in $a_1$ with the elements in $b_1$, and pair the elements in $a_2$ with the elements in $b_2$, and then perform operations. During the pairing process, we can use a greedy strategy, pairing the smaller elements in $a_i$ with the smaller elements in $b_i$ each time, which can ensure the minimum number of operations. This can be directly implemented through sorting.
Since each operation can reduce the difference of the corresponding elements by $4$, we accumulate the difference of each corresponding position, and finally divide by $4$ to get the answer.
The time complexity is $O(n \times \log n)$, where $n$ is the length of the array $nums$.
1 2 3 4 5 |
|
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 27 28 29 30 31 32 |
|
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 27 |
|