Question

ACM一道算法题，我的算法为何WA

Description

There is N pairs of balls in a small box. That means the number for each pair is the same. However, for some reason, a ball is lost. Now, you will get the number of the rest. Can you find the number of the lost ball as fast as possible?

Input

The input consists of several test cases. For each case, the first line contains an integer N(1<= N <= 500000), the total number of toys in the field. Then a line follow, which contains 2*N-1 numbers, which will is positive and not exceed 2*10^9. The input is terminated by N=0.

Output

For each test case, print in one line the number of the lost ball.

Sample Input

3
2 4 5 4 5
5
199 342 199 341 332 340 332 342 340
0

Sample Output

2
341
不用异或算法，就用正常的哈希表存储，把余数相同的归为一类形成一个链表，然后用链表操作来实现重复删除或插入等

Answer 1

楼主的算法应该是没有问题的，问题可能出在具体的实现上，因为没有代码，也不好推断问题所在。

刚才实现了楼主的算法，结果也是WA。
遂又尝试了一下二叉排序树法，依然WA……
然后呢，我把两种方法都进行了下改进，设置了检查条件，如果有超过一个不成对的数字出现，就进入死循环，结果是，两种算法都会超时。
所以，说一下我的猜测（对，是猜测，因为我不能完全保证我的算法实现了我的想法，也就不能证明我的推测是正确的），那就是，测试数据并不像题目描述那样，除一个数字之外，其余全部两两成对。
异或的算法确实能保证在数据如题目描述的情况下求得正确答案，但它在数据错误时也能得出一个解，并且无法检查数据的正确性。
所以，我再进行一个大胆的猜想，这道题目的数据制作者，是假定了这样一种算法为正确解法，然后呢，用了某种不能保证符合题目描述的方法生成了测试数据，再用这种算法得到了参考答案，却没有用其它算法进行验证……
通过观察这道题的统计数据，我猜大概绝大多数的人都是用这种算法通过的。

再次重申，以上猜测未经严格验证。楼主如果有兴趣，也可以自己试一下:)

Answer 2

为什么要这么麻烦？把前n个数加起来所得的和，减去后n-1个数的和，不就是答案了吗？（不过求和的时候记得用long long类型，否则hold不住。）