Article From:

Title Description

After a period of stressful preparation, the computer group’s “RP restaurant” finally opened, and the manager, LXC, received a large order for dinner. The staff worked together to prepare for the package when they were preparing to deliver. Suddenly, they encountered a difficult problem, chopsticks! CX children find outAll the chopsticks in the dining room, but unfortunately the chopsticks are different, and we all know that the chopsticks need the same length to make up a pair. More troublesome is that the number of chopsticks found by CX is odd, but only one of these chopsticks is a single chopstick, the rest are double, kind youCan you help CX find out the length of the chopsticks?

Input-output format

Input format:


The first line reads a number N, which represents the root number of the chopsticks found by CX.

The second line is the number of N spaced apart, representing the length of chopsticks.


Output format:


One line, the length of the chopsticks.


Input and output sample

Input sample #1:

2 2 1 3 3 3 2 3 1
Output sample #1:



For 80% of the data, N< =100000;

For 100% of the data, N< =10000000.

Make complaints

  Today, I failed to get the result of the college entrance examination. Not to say… Do a way to ease the mood.

The idea of solving the problem

  See the first idea of this problem, fast row, and then two two pushed back, complexity $O (NlogN) $, exploded (although data water can pass). Second ideas, bucket row, and then sweep again to find odd numbers, but don’t know how long the longest chopsticks are, emmmm, discretization, complexity.$O (NlogN) $, and it has been blown up (though data can be used for water). And then… So there’s no way of thinking. Look at the solution and learn something that was previously known and forgotten: a^a=0, 0^a=a (^ XOR, Xor). So the length of all the length or up, finally knotThe answer is.

source code

 1 #include<stdio.h>
 3 int main()
 4 {
 5     int ans=0,n;
 6     scanf("%d",&n);
 7     for(int i=1,j;i<=n;i++)
 8     {
 9         scanf("%d",&j);
10         ans^=j;
11     }
12     printf("%d",ans);
13     return 0;
14 }


Leave a Reply

Your email address will not be published. Required fields are marked *