Online Programming Server
Problem 1099: Find the majority
| Problem ID | 1099 |
|---|---|
| Title | Find the majority |
| Description | Heckson is the administrator of the Silver Forum. In each month, all users will vote for their most favorite user. After collecting the votes, if there exists a user voted by more than half of the users, then he will become the Star of the Month. If no such user exists, then there is no Star of the Month at that month. Your task is to help Heckson.
|
| Input | The first line contains an integer T (1 ≤ T ≤ 20), the number of months. Each test cases starts with an integer N (1 ≤ N ≤ 100000), the number of users. The users' id are labeled from 1 to 109, inclusively. The next line will contains N integers, the votes. |
| Output | For each test case, output a user id of the Star of the Month. If there is no Star of the Month at that month, then output -1. |
| Sample Input | 2 5 5 2 1 2 2 6 1 2 3 4 5 6 |
| Sample Output | 2 -1 |
| Hint | There is a linear time algorithm. |
| Last Modified | 2012-05-31 12:55:43 |
| Time Limit | 1 seconds |
| Memory Limit | 64 MB |
| Accepted Solutions | 1 |
| Submitted Solutions | 2 |
| Difficulty Factor | 331 |
Facebook