All Tracks Basic Programming Implementation Basics of Implementation Problem

Equal Median
Tag(s):

Basic Programming, Basics of Implementation, Implementation, Medium

Problem
Editorial
Analytics

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”.

SAMPLE INPUT
1
7
1 2 3 3 5 6 7
4 6 8 8 9 9 9
SAMPLE OUTPUT
2
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?