Skip to content

2449. Minimum Number of Operations to Make Arrays Similar 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  long long makeSimilar(vector<int>& nums, vector<int>& target) {
    long 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);

    sort(begin(A[0]), end(A[0]));
    sort(begin(A[1]), end(A[1]));
    sort(begin(B[0]), end(B[0]));
    sort(begin(B[1]), end(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;
  }
};

 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
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;
  }
}

1
2
3
4
5
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