Equal Median

4.1

20 votes
Basic Programming, Basics of Implementation, Implementation, Medium
Problem

You will be given two arrays A and B of odd length N. In one swap operation, you can select a number from A and another number from B and swap them. You need to find the minimum number of swap operations required so that the median of those two arrays become equal. The median of the array is the element at the middle position in ascending order.

Constraints

  • 1 <= T <= 10
  • 1 <= N <= 10^5
  • 0 <= Ai, Bi <= 10^9

Note: N will always be an odd number.

Input Format

The first line contains T, the number of test cases. The first line of a test case contains an integer N. The second line contains N space separated integers representing the array A, and the third line contains N space separated integers representing the array B.

Output Format

For each test cases, print a single integer, the minimum number of swap operations necessary to make the median of those two arrays equal. If there’s no solution then print “-1”.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Explanation of 1st case

We just need two swap operations.

First swap operation:
Take 1 from A and 9 from B and swap them.
Now the arrays look like this: A = [2, 3, 3, 5, 6, 7, 9] and B = [1, 4, 6, 8, 8, 9, 9].

Second swap operation:
Take 2 from A and 9 from B and swap them.
Now the arrays look like this: A = [3, 3, 5, 6, 7, 9, 9] and B = [1, 2, 4, 6, 8, 8, 9].
Now the median of both arrays is 6.

Editor Image

?