First I want you to read the task and try to solve it in linear time complexity, and minimum memorize complexity.

Lonely Integer
There are N integers in an array A. All but one integer occurs in pairs. Your task is to find out the number that occurs only once.

Input Format

The first line of the input contains an integer N indicating number of integers in the array A. The next line contains N integers each separated by a single space. Constraints 1 <= N < 100 N % 2 = 1 ( N is an odd number ) 0 <= A[i] <= 100, ∀ i ∈ [1, N]

Output Format

Output S, the number that occurs only once.
Sample Input
3
1 1 2
Sample Output
2

If you don't have any idea I will write a code.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
 	int N;
	cin >> N;
	int tmp, result = 0;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		result ^= tmp;
	}
	cout << result;
    return 0;
}

Cool trick using only xor operation, but I can't prove why that work. Can anyone prove it?