SPOJ-OLOLO: Onotole needs your help

問題概要

長さN(<5*10^5)の数列が与えられる。ある一つの数は1回しか出現せず、それ以外の数は必ず2回現れる。1回だけ出現する数を求める問題。

解法

2回出てくる数が打ち消されるような操作をすれば良い。もう少し具体的には、自分自身が自分自身の逆元となるような演算を決めて、単位元に加えつづければ良い。そのような操作は、例えばxorで実現できる。

acceptされたコード

計算量O(N)。

#include <cstdio>
using namespace std;

int main(){
	int N, x, ans = 0;
	scanf("%d\n", &N);
	for(int i=0; i<N; i++){
		scanf("%d",&x);
		ans ^= x;
	}
	printf("%d\n", ans);

	return 0;
}