# Minimum Number of Operations to Make Arrays Similar
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-arrays-similar)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-arrays-similar
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## Problem
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 to `target`.

# Approaches
## Brute-Force by Trying All Pairings
This approach attempts to solve the problem by exploring every possible way to pair the numbers from `nums` with the numbers from `target`. Since numbers can only be transformed into other numbers of the same parity, we only need to consider pairings within the odd and even groups. The method calculates the transformation cost for every single permutation of pairings and finds the minimum among them.
**Time:** O(k! * k + (n-k)! * (n-k)), where `k` is the number of odd elements. This is prohibitively slow. · **Space:** O(n), to store the separated lists for odd and even numbers and the permutations.
**Pros:** Demonstrates a basic understanding of the problem's combinatorial nature.
**Cons:** Extremely high time complexity, making it infeasible for all but the smallest input sizes.; Complex to implement correctly due to the need for permutation generation.
### Explanation
The fundamental observation is that an operation `nums[i] += 2, nums[j] -= 2` preserves the parity of both `nums[i]` and `nums[j]`. This means we can consider the problem of transforming the odd numbers in `nums` to the odd numbers in `target` separately from the even numbers. 

This brute-force approach enumerates all possible one-to-one mappings (permutations) from the odd numbers in `nums` to the odd numbers in `target`, and similarly for the even numbers. For each complete mapping, it calculates the total number of operations required. The total increase needed is the sum of all positive differences `(target_val - nums_val)`. Since each operation provides a `+2` increase, the number of operations is this sum divided by 2. The algorithm finds the minimum cost over all possible permutations.

However, the number of permutations is `k!` (k-factorial), where `k` is the number of elements in the list. Given that `n` can be up to `10^5`, this approach is computationally impossible in practice.
### Algorithm
- Separate the `nums` and `target` arrays into four lists based on parity: `nums_odd`, `nums_even`, `target_odd`, and `target_even`.
- Initialize a variable `min_operations` to a very large value.
- Generate all possible permutations of the `target_odd` list.
- For each permutation of `target_odd`:
  - Generate all possible permutations of the `target_even` list.
  - For each permutation of `target_even`:
    - Calculate the total positive difference required to transform `nums` into this pairing. This is done by summing up `max(0, p_odd[i] - nums_odd[i])` for all `i` in the odd lists and `max(0, p_even[i] - nums_even[i])` for all `i` in the even lists.
    - The number of operations for this specific pairing is the total positive difference divided by 2.
    - Update `min_operations` with the minimum value found so far.
- Return `min_operations`.

## Greedy Approach with Sorting
A much more efficient approach is based on a greedy strategy. After separating the numbers by parity, we sort both the `nums` and `target` sub-lists. The key insight is that to minimize the total number of operations, we should pair the smallest numbers with the smallest, the second smallest with the second smallest, and so on. This is because this pairing minimizes the sum of absolute differences, which in turn minimizes the total increase required. The total number of operations is then half of the total increase needed across all numbers.
**Time:** O(n log n), dominated by the sorting of the odd and even sub-lists. Separating the numbers takes O(n) and calculating the final sum takes O(n). · **Space:** O(n), for storing the four lists of odd and even numbers. In the worst case, one pair of lists can contain up to n elements.
**Pros:** Highly efficient with a time complexity of O(n log n).; Guaranteed to find the minimum number of operations.; The logic is straightforward and relatively easy to implement.
**Cons:** Requires O(n) extra space to hold the separated lists.
### Explanation
This approach leverages two key insights. First, since operations preserve parity, we can handle odd and even numbers as two independent subproblems. Second, the minimum number of operations is achieved by a greedy pairing strategy. To minimize the sum of transformations, it's always optimal to transform the i-th smallest number in `nums` (of a certain parity) to the i-th smallest number in `target` (of the same parity). This is a known property related to the rearrangement inequality.

The algorithm proceeds as follows:
1. Segregate `nums` and `target` into lists of odd and even numbers.
2. Sort these four lists. This allows us to easily pair the i-th smallest elements.
3. Calculate the total increase required. We iterate through the sorted lists and sum up all the positive differences (`target[i] - nums[i] > 0`). Let this be `positive_diff_sum`.
4. The total decrease required will be equal to the total increase required because the sum of elements in `nums` and `target` are equal. Each operation consists of one `+2` and one `-2`. Therefore, the total number of operations is simply the total increase needed divided by 2.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public long minOperations(int[] nums, int[] target) {
        List<Integer> numsOdd = new ArrayList<>();
        List<Integer> numsEven = new ArrayList<>();
        List<Integer> targetOdd = new ArrayList<>();
        List<Integer> targetEven = new ArrayList<>();

        for (int num : nums) {
            if (num % 2 == 0) {
                numsEven.add(num);
            } else {
                numsOdd.add(num);
            }
        }

        for (int num : target) {
            if (num % 2 == 0) {
                targetEven.add(num);
            } else {
                targetOdd.add(num);
            }
        }

        Collections.sort(numsOdd);
        Collections.sort(numsEven);
        Collections.sort(targetOdd);
        Collections.sort(targetEven);

        long positiveDiffSum = 0;

        for (int i = 0; i < numsOdd.size(); i++) {
            int diff = targetOdd.get(i) - numsOdd.get(i);
            if (diff > 0) {
                // The difference must be even. We add half of it to the count of operations.
                positiveDiffSum += diff;
            }
        }

        for (int i = 0; i < numsEven.size(); i++) {
            int diff = targetEven.get(i) - numsEven.get(i);
            if (diff > 0) {
                positiveDiffSum += diff;
            }
        }

        // Each operation increases one number by 2. The total increase needed is positiveDiffSum.
        // So, the number of operations is positiveDiffSum / 2.
        return positiveDiffSum / 2;
    }
}
```
### Algorithm
- Create four lists: `nums_odd`, `nums_even`, `target_odd`, and `target_even`.
- Iterate through the input arrays `nums` and `target`. Populate the four lists by checking the parity of each number.
- Sort all four lists in ascending order.
- Initialize a `long` variable `positive_diff_sum` to 0.
- Iterate through the sorted odd lists from `i = 0` to `nums_odd.size() - 1`. Calculate the difference `d = target_odd.get(i) - nums_odd.get(i)`. If `d` is positive, add it to `positive_diff_sum`.
- Iterate through the sorted even lists from `i = 0` to `nums_even.size() - 1`. Calculate the difference `d = target_even.get(i) - nums_even.get(i)`. If `d` is positive, add it to `positive_diff_sum`.
- The total minimum number of operations is `positive_diff_sum / 2`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  long makeSimilar(int[] nums, int[] target) {
    Arrays.sort(nums);
    Arrays.sort(target);
    List<Integer> a1 = new ArrayList<>();
    List<Integer> a2 = new ArrayList<>();
    List<Integer> b1 = new ArrayList<>();
    List<Integer> b2 = new ArrayList<>();
    for (int v : nums) {
      if (v % 2 == 0) {
        a1.add(v);
      } else {
        a2.add(v);
      }
    }
    for (int v : target) {
      if (v % 2 == 0) {
        b1.add(v);
      } else {
        b2.add(v);
      }
    }
    long ans = 0;
    for (int i = 0; i < a1.size(); ++i) {
      ans += Math.abs(a1.get(i) - b1.get(i));
    }
    for (int i = 0; i < a2.size(); ++i) {
      ans += Math.abs(a2.get(i) - b2.get(i));
    }
    return ans / 4;
  }
}

```

### Python

```python
class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int: nums . sort(key=lambda x: (x & 1, x)) target . sort(key=lambda x: (x & 1, x)) return sum(abs(a - b) for a, b in zip(nums, target)) // 4

```

### CPP

```cpp
class Solution { public: long long makeSimilar ( vector < int >& nums , vector < int >& target ) { sort ( nums . begin (), nums . end ()); sort ( target . begin (), target . end ()); vector < int > a1 ; vector < int > a2 ; vector < int > b1 ; vector < int > b2 ; for ( int v : nums ) { if ( v & 1 ) a1 . emplace_back ( v ); else a2 . emplace_back ( v ); } for ( int v : target ) { if ( v & 1 ) b1 . emplace_back ( v ); else b2 . emplace_back ( v ); } long long ans = 0 ; for ( int i = 0 ; i < a1 . size (); ++ i ) ans += abs ( a1 [ i ] - b1 [ i ]); for ( int i = 0 ; i < a2 . size (); ++ i ) ans += abs ( a2 [ i ] - b2 [ i ]); return ans / 4 ; } };
```