Minimum Number of Operations to Make Arrays Similar
Minimum Number of Operations to Make Arrays Similar is a hard arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (split by parity, sort, pair up), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (match by repeated scanning) up.
Problem
You are given two positive integer arrays nums and target of the same length. In one operation you pick two different indices i and j and do nums[i] += 2 and nums[j] -= 2 at the same time.
The two arrays are similar when each value occurs the same number of times in both (order does not matter). Return the minimum number of operations needed to make nums similar to target. The input always allows this.
Examples
Example 1
- Input
nums = [9, 4, 2], target = [5, 6, 4]- Output
2- Why
- Lower 9 by 2 while raising 2 to 4, then lower 7 to 5 while raising 4 to 6. nums becomes [5, 6, 4], which has the same values as target.
Example 2
- Input
nums = [1, 3, 5], target = [5, 1, 3]- Output
0- Why
- Both arrays already contain the same values, only in a different order.
Example 3
- Input
nums = [10, 1, 2, 7], target = [4, 3, 6, 7]- Output
2- Why
- Odd values pair as 1→3 and 7→7, even values as 2→4 and 10→6. The total surplus is 4, and every operation removes 2 of it.
Constraints
n == nums.length == target.length,1 <= n <= 10^51 <= nums[i], target[i] <= 10^6- It is guaranteed that
numscan always be made similar totarget.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (match by repeated scanning) | O(n²) | O(n) |
| Optimal (split by parity, sort, pair up) | O(n log n) | O(n) |
1Brute force (match by repeated scanning)
O(n²)Each of the n values scans all n targets.O(n)The used flags.Within each parity class, matching the smallest value with the smallest target, the next with the next, and so on, is optimal. Build that matching without sorting the targets: take the values in ascending order and, for each, scan for the smallest unused target of the same parity. Add up the positive differences; every operation removes exactly 2 of that surplus.
- Sort nums. Mark every target as unused.
- For each value v in nums, scan target for the smallest unused t with the same parity as v; mark it used.
- If v > t, add v - t to surplus.
- Return surplus / 2.
class Solution {
public long makeSimilar(int[] nums, int[] target) {
int n = nums.length;
int[] a = nums.clone();
Arrays.sort(a);
boolean[] used = new boolean[n];
long surplus = 0;
for (int v : a) {
int best = -1;
for (int j = 0; j < n; j++)
if (!used[j] && target[j] % 2 == v % 2 && (best == -1 || target[j] < target[best])) best = j;
used[best] = true;
if (v > target[best]) surplus += v - target[best];
}
return surplus / 2;
}
}class Solution:
def makeSimilar(self, nums: List[int], target: List[int]) -> int:
n = len(nums)
used = [False] * n
surplus = 0
for v in sorted(nums):
best = -1
for j in range(n):
if not used[j] and target[j] % 2 == v % 2 and (best == -1 or target[j] < target[best]):
best = j
used[best] = True
if v > target[best]:
surplus += v - target[best]
return surplus // 2class Solution {
public:
long long makeSimilar(vector<int>& nums, vector<int>& target) {
int n = nums.size();
vector<int> a(nums);
sort(a.begin(), a.end());
vector<bool> used(n, false);
long long surplus = 0;
for (int v : a) {
int best = -1;
for (int j = 0; j < n; j++)
if (!used[j] && target[j] % 2 == v % 2 && (best == -1 || target[j] < target[best])) best = j;
used[best] = true;
if (v > target[best]) surplus += v - target[best];
}
return surplus / 2;
}
};function makeSimilar(nums, target) {
const n = nums.length;
const a = [...nums].sort((x, y) => x - y);
const used = new Array(n).fill(false);
let surplus = 0;
for (const v of a) {
let best = -1;
for (let j = 0; j < n; j++)
if (!used[j] && target[j] % 2 === v % 2 && (best === -1 || target[j] < target[best])) best = j;
used[best] = true;
if (v > target[best]) surplus += v - target[best];
}
return surplus / 2;
}2Optimal (split by parity, sort, pair up)
O(n log n)Two sorts plus one linear pass.O(n)Sorted copies of the arrays.Separate both arrays into odd and even values and sort each of the four lists. Pair the i-th odd value with the i-th odd target and the i-th even value with the i-th even target (sorted pairing never crosses, so it minimises the total movement). Each operation moves 2 units from one surplus to one deficit, so the answer is the total surplus divided by 2.
- Sort nums and target with odd values first, then even values, each part ascending (a comparator on (parity, value) does this).
- For each index i, if nums[i] > target[i], add the difference.
- Return the sum / 2.
class Solution {
public long makeSimilar(int[] nums, int[] target) {
int[] a = order(nums), b = order(target);
long surplus = 0;
for (int i = 0; i < a.length; i++)
if (a[i] > b[i]) surplus += a[i] - b[i];
return surplus / 2;
}
private int[] order(int[] x) {
int[] r = x.clone();
// odd values become negative, so they sort first, then evens; both parts ascending
for (int i = 0; i < r.length; i++) if (r[i] % 2 == 1) r[i] = r[i] - 2_000_000;
Arrays.sort(r);
for (int i = 0; i < r.length; i++) if (r[i] < 0) r[i] += 2_000_000;
return r;
}
}class Solution:
def makeSimilar(self, nums: List[int], target: List[int]) -> int:
a = sorted(nums, key=lambda v: (v % 2 == 0, v))
b = sorted(target, key=lambda v: (v % 2 == 0, v))
return sum(x - y for x, y in zip(a, b) if x > y) // 2class Solution {
public:
long long makeSimilar(vector<int>& nums, vector<int>& target) {
vector<int> a = order(nums), b = order(target);
long long surplus = 0;
for (size_t i = 0; i < a.size(); i++)
if (a[i] > b[i]) surplus += a[i] - b[i];
return surplus / 2;
}
private:
vector<int> order(const vector<int>& x) {
vector<int> r(x);
for (int& v : r) if (v % 2 == 1) v -= 2000000;
sort(r.begin(), r.end());
for (int& v : r) if (v < 0) v += 2000000;
return r;
}
};function makeSimilar(nums, target) {
const order = (x) => Int32Array.from(x, (v) => (v % 2 === 1 ? v - 2000000 : v)).sort().map((v) => (v < 0 ? v + 2000000 : v));
const a = order(nums), b = order(target);
let surplus = 0;
for (let i = 0; i < a.length; i++)
if (a[i] > b[i]) surplus += a[i] - b[i];
return surplus / 2;
}Edge cases to test
- Already similar (possibly in a different order): 0
- A single element: it must already match, so 0
- Only odd or only even values
- Large values and large n, where the answer needs 64 bits
Hints
Hint 1
Adding or subtracting 2 never changes a number's parity, so odd values can only turn into odd target values, and even into even.
Hint 2
Within one parity class, which value should become which target value? Exchanging two assignments never helps if you match them in sorted order.
Hint 3
Each operation lowers the total positive gap by exactly 2, so the answer is (sum of positive differences) / 2.
FAQ
What is the best time complexity for Minimum Number of Operations to Make Arrays Similar?
Optimal (split by parity, sort, pair up) runs in O(n log n) time and O(n) extra space. Two sorts plus one linear pass.
Which pattern does Minimum Number of Operations to Make Arrays Similar use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Minimum Number of Operations to Make Arrays Similar?
Yes. Brute force (match by repeated scanning) takes O(n²) time and O(n) space. Within each parity class, matching the smallest value with the smallest target, the next with the next, and so on, is optimal.
Which edge cases should I test for Minimum Number of Operations to Make Arrays Similar?
Already similar (possibly in a different order): 0; A single element: it must already match, so 0; Only odd or only even values; Large values and large n, where the answer needs 64 bits.