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; }