### lovro-sinda's blog

By lovro-sinda, 7 years ago,

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?

• -20

 » 7 years ago, # | ← Rev. 5 →   0 http://codeforces.com/blog/entry/12534Same proof with this.x xor x = 0 So xor all numbers. If a number is xor twice, number doesn't change anything.
 » 7 years ago, # |   +4
 » 7 years ago, # |   +2 The proof follows from properties of xor: a^b=b^a a^a=0 a^0=a The first one lets us reorder the numbers in any way without the xor being affected. Then, we get the xor as (a^a)^(b^b)^(c^c)^...^(r^r)^s, which is 0^0^0^...^0^s=s.Also, the linear time complexity is caused by computers being constructed to do bitwise operations in O(1). If you did it on paper, your complexity would be . It's a cool trick nevertheless.
•  » » 7 years ago, # ^ |   +10 Actually for reodering numbers we need one more property: a^(b^c)=(a^b)^c
 » 4 years ago, # |   0 awesome, can we have more of these ?