Given an odd list of couples of numbers (each number appears twice), find the number that occurs only once.
The solution is a mere xor on all the numbers as:
Also, xor is commutative:
so if we have a sample input A, B, C, A, B:
C++ implementation:
#include <iostream> #include <fstream> #include <iomanip> using namespace std; #define N 1024 typedef unsigned long long int64; int n, g; int64 card, cardXor; ofstream ofile; ifstream ifile; int main() { int i, j; ifile.open("in.txt"); ofile.open("out.txt"); ifile >> n; for (i = 0; i < n; ++i) { // init cardXor = 0; // in ifile >> g; for (j = 0; j < g; cardXor ^= card, ++j) ifile >> card; // out ofile << "Case #" << i + 1 << ": " << cardXor << endl; } return 0; }