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 makenums similar totarget. The test cases are generated such that nums can always be similar to target.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7


    
    
    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 <= 10^5
  • 1 <= nums[i], target[i] <= 10^6
  • It is possible to make nums similar to target.

Solution

Method 1 – Greedy Pairing by Parity

Intuition

Since we can only add/subtract 2, the parity of each element is preserved. We need to match even numbers in nums to even numbers in target, and odd to odd. Sort both arrays by parity, pair them, and sum the differences divided by 2.

Approach

  1. Split nums and target into even and odd arrays.
  2. Sort each subarray.
  3. For each pair, sum the absolute difference divided by 2.
  4. The answer is the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        vector<int> ne, no, te, to;
        for (int x : nums) (x % 2 ? no : ne).push_back(x);
        for (int x : target) (x % 2 ? to : te).push_back(x);
        sort(ne.begin(), ne.end()); sort(no.begin(), no.end());
        sort(te.begin(), te.end()); sort(to.begin(), to.end());
        long long ans = 0;
        for (int i = 0; i < ne.size(); ++i) ans += abs(ne[i] - te[i]) / 2;
        for (int i = 0; i < no.size(); ++i) ans += abs(no[i] - to[i]) / 2;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import "sort"
func makeSimilar(nums, target []int) int64 {
    ne, no, te, to := []int{}, []int{}, []int{}, []int{}
    for _, x := range nums {
        if x%2 == 0 { ne = append(ne, x) } else { no = append(no, x) }
    }
    for _, x := range target {
        if x%2 == 0 { te = append(te, x) } else { to = append(to, x) }
    }
    sort.Ints(ne); sort.Ints(no); sort.Ints(te); sort.Ints(to)
    var ans int64
    for i := range ne { ans += int64(abs(ne[i]-te[i]) / 2) }
    for i := range no { ans += int64(abs(no[i]-to[i]) / 2) }
    return ans
}
func abs(x int) int { if x < 0 { return -x } else { return x } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public long makeSimilar(int[] nums, int[] target) {
        List<Integer> ne = new ArrayList<>(), no = new ArrayList<>();
        List<Integer> te = new ArrayList<>(), to = new ArrayList<>();
        for (int x : nums) (x % 2 == 0 ? ne : no).add(x);
        for (int x : target) (x % 2 == 0 ? te : to).add(x);
        Collections.sort(ne); Collections.sort(no);
        Collections.sort(te); Collections.sort(to);
        long ans = 0;
        for (int i = 0; i < ne.size(); ++i) ans += Math.abs(ne.get(i) - te.get(i)) / 2;
        for (int i = 0; i < no.size(); ++i) ans += Math.abs(no.get(i) - to.get(i)) / 2;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun makeSimilar(nums: IntArray, target: IntArray): Long {
        val ne = mutableListOf<Int>(); val no = mutableListOf<Int>()
        val te = mutableListOf<Int>(); val to = mutableListOf<Int>()
        for (x in nums) if (x % 2 == 0) ne.add(x) else no.add(x)
        for (x in target) if (x % 2 == 0) te.add(x) else to.add(x)
        ne.sort(); no.sort(); te.sort(); to.sort()
        var ans = 0L
        for (i in ne.indices) ans += kotlin.math.abs(ne[i] - te[i]) / 2
        for (i in no.indices) ans += kotlin.math.abs(no[i] - to[i]) / 2
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def makeSimilar(self, nums: list[int], target: list[int]) -> int:
        ne = sorted(x for x in nums if x % 2 == 0)
        no = sorted(x for x in nums if x % 2)
        te = sorted(x for x in target if x % 2 == 0)
        to = sorted(x for x in target if x % 2)
        ans = sum(abs(a - b) // 2 for a, b in zip(ne, te))
        ans += sum(abs(a - b) // 2 for a, b in zip(no, to))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn make_similar(nums: Vec<i32>, target: Vec<i32>) -> i64 {
        let mut ne: Vec<i32> = nums.iter().filter(|&&x| x % 2 == 0).cloned().collect();
        let mut no: Vec<i32> = nums.iter().filter(|&&x| x % 2 != 0).cloned().collect();
        let mut te: Vec<i32> = target.iter().filter(|&&x| x % 2 == 0).cloned().collect();
        let mut to: Vec<i32> = target.iter().filter(|&&x| x % 2 != 0).cloned().collect();
        ne.sort(); no.sort(); te.sort(); to.sort();
        let mut ans = 0i64;
        for (a, b) in ne.iter().zip(te.iter()) { ans += (a - b).abs() as i64 / 2; }
        for (a, b) in no.iter().zip(to.iter()) { ans += (a - b).abs() as i64 / 2; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    makeSimilar(nums: number[], target: number[]): number {
        const ne = nums.filter(x => x % 2 === 0).sort((a, b) => a - b);
        const no = nums.filter(x => x % 2 !== 0).sort((a, b) => a - b);
        const te = target.filter(x => x % 2 === 0).sort((a, b) => a - b);
        const to = target.filter(x => x % 2 !== 0).sort((a, b) => a - b);
        let ans = 0;
        for (let i = 0; i < ne.length; ++i) ans += Math.abs(ne[i] - te[i]) / 2;
        for (let i = 0; i < no.length; ++i) ans += Math.abs(no[i] - to[i]) / 2;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — n = length of nums, for sorting.
  • 🧺 Space complexity: O(n) — for subarrays.