In an array of integers, all elements appear even times except one appears odd times. Find that element. Please give an O(n)-time algorithm. For example: input array: [1,2,3,3,2,1,1,1,2], should output 2

Expert Answer
Darshan
Darshan answered this Was this answer helpful?
0
0
104 answers
The best solution without using any memory is use Bitwise XOR Operator and XOR all the elements , so if you XOR all the elements the output will be the element that apper odd times.

Because XOR of element with itself is 0. ( e.g 1 XOR 1 = 0 ), so the only odd element will be left at last.

Algorithm:

int getOddNumber(int ar[], int size)

{

int i;

int out = 0;

for (i=0; i < size; i++){

out = out ^ ar[i]; // XOR operation

}

return out;

}