REPEAT - Find the unique Number

There will be odd number of element in array, and each number has a pair except one element. Find that unique element

Input

T = number of test cases

N = size of array

a1, a2, ... an array element

Output

Unique number

Example

Input:
2
5
2 1 2 3 1
7
3 3 5 4 5 4 5

Output: 3
5

limit:
T<=100
N<=10^5
ai <= 10^10

Added by:pankaj
Date:2011-02-10
Time limit:0.300s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2016-10-02 08:52:09
I am finding the XOr of all the numbers by taking them in a tree and the time is of the order O(log(n))...Yet getting TLE plz help
2016-06-19 14:37:46
can anybody tell, is this a question of maps?
2011-04-26 16:09:04 Robert Gerbicz
Ok, now I've found the trick.
2011-04-26 15:52:05 Piotr KÄ…kol
@Robert Gerbicz - Yes, it is. Please think about it more because the algorithm is quite interesting. :-)

Edit: This task is a copy of OLOLO.

Last edit: 2011-04-26 15:55:13
2011-04-26 15:43:47 Robert Gerbicz
Without fwrite it is impossible to solve it. And the problem description is totally bad. You have to find the number that appears odd times.
2011-03-27 20:30:47 LeppyR64
There will not likely be N items on one line. These N items will be spread over multiple lines.
2011-03-25 22:19:20 Hugo Felipe Bueno
Is there some kind of special case one must be aware of? I've tried everything I can come up with and the only WA I've gotten is from the judge.

Last edit: 2011-03-25 22:20:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.