Lonely element

Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once.
Devise an algorithm to find the lonely element.

Ex : {1 2 4 5 1 4 2}
Answer : 5

Solution :

Note the properties of XOR :

1. A ^ A = 0
2. 0 ^ A = A
3. A ^ (B ^ C) = (A ^ B) ^ C

Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice.

Complexity :

• Time : O(N)
• Space : O(1)

Code :

int lonely_element(int input[], int N){

int result=0, i=0;

for(i=0; i<N; i++)

result ^= input[i];

return result;

}