Team division
Practice
3.8 (10 votes)
Greedy algorithms
Algorithms
Basics of greedy algorithms
Greedy algorithm
Problem
91% Success 1398 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code

There are N (where N is always even) players standing in a line where the coordinates of players are given as $$(X1,0), (X2,0)... (XN,0).Youarerequiredtodividethemintotwoteamssuchthatthereisanequalnumberofplayersoneitherside.Forthis,youcanselectacoordinate(P, 0)ifandonlyifthenumberofplayersontheleft−handsideisequaltothenumberofplayersontheright−handside.Fortheplayerson(P,0)$$, you are independent to choose their side.
Find the number of such possible coordinates where teams can be divided.

Note: Non-integral coordinates do not exist.

Input format

  • The first line contains an integer T denoting the number of test cases.
  • For each test case:
    • The first line contains an integer N denoting the number of players.
    • The second line contains an array of space-separated integers denoting array X.

Output format

Print a single line for each test case, denoting the number of coordinates (P,0) from where the teams can be divided.

Constraints

1≤T≤20000

1≤N≤200000

0≤|Xi|≤109

Here, N is always even.

The sum of N over all test cases does not exceed 200000.

Sample Input
2
4
3 -3 1 -2
2
2 2
Sample Output
4
1
Explanation

First test case:

First test case:

All the players are indicated by an line below the number, all the points which colored black above the number line is suitable for the team division, but we need to consider the only integer co-ordinates, so there are 4 {-2,-1,0,1}.
 

Note that while considering -2,  we can decide which side we want to keep player at -2 and for division we will consider him on left.

Second test case:

Both the players are at 2, so the point we can choose is 2, we can decide to keep one player on left and one player on the right.

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
1.Little Jhool and his punishment
Points:20
21 votes
Tags:
ApprovedBasic ProgrammingEasyGreedy AlgorithmsOpen
2.Minimum Cost
Points:20
5 votes
Tags:
Greedy AlgorithmsAlgorithmsBasics of Greedy Algorithms
3.Swap It
Points:20
34 votes
Tags:
AlgorithmsApprovedEasyGreedy AlgorithmsOpen
Editorial

Login to unlock the editorial