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”.
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor