2449. Minimum Number of Operations to Make Arrays Similar LeetCode Solution
In this guide, you will get 2449. Minimum Number of Operations to Make Arrays Similar LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make Arrays Similar problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Operations to Make Arrays Similar
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.
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 to target.
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
2449. Minimum Number of Operations to Make Arrays Similar LeetCode Solution in C++
class Solution {
public:
long long makeSimilar(vector<int>& nums, vector<int>& target) {
long ans = 0;
vector<vector<int>> A(2); // A[0] := even nums, A[1] := odd nums
vector<vector<int>> B(2); // B[0] := even target, B[1] := odd nums
for (const int num : nums)
A[num % 2].push_back(num);
for (const int num : target)
B[num % 2].push_back(num);
ranges::sort(A[0]);
ranges::sort(A[1]);
ranges::sort(B[0]);
ranges::sort(B[1]);
for (int i = 0; i < 2; ++i)
for (int j = 0; j < A[i].size(); ++j)
ans += abs(A[i][j] - B[i][j]) / 2;
return ans / 2;
}
}; /* code provided by PROGIEZ */
2449. Minimum Number of Operations to Make Arrays Similar LeetCode Solution in Java
class Solution {
public long makeSimilar(int[] nums, int[] target) {
long ans = 0;
// A[0] := even nums, A[1] := odd nums
List<Integer>[] A = new List[] {new ArrayList<>(), new ArrayList<>()};
// B[0] := even target, B[1] := odd nums
List<Integer>[] B = new List[] {new ArrayList<>(), new ArrayList<>()};
for (final int num : nums)
A[num % 2].add(num);
for (final int num : target)
B[num % 2].add(num);
Collections.sort(A[0]);
Collections.sort(A[1]);
Collections.sort(B[0]);
Collections.sort(B[1]);
for (int i = 0; i < 2; ++i)
for (int j = 0; j < A[i].size(); ++j)
ans += Math.abs(A[i].get(j) - B[i].get(j)) / 2;
return ans / 2;
}
} // code provided by PROGIEZ
2449. Minimum Number of Operations to Make Arrays Similar LeetCode Solution in Python
class Solution:
def makeSimilar(self, nums: list[int], target: list[int]) -> int:
nums.sort(key=lambda x: (x % 2, x))
target.sort(key=lambda x: (x % 2, x))
return sum(abs(a - b) for a, b in zip(nums, target)) // 4 # code by PROGIEZ
