It can be done in O(n) time using a hash table as shown by the following
pseudo code:
function FindEvenRepeter(arr[])
hash_table = empty
sum = 0
for x in arr
if (x is present in hash_table)
sum = sum ^ x
else
add x to hash_table
return sum
As Piyush correctly said, using XOR operation we can find a number that
repeats odd number of times in an array in which other numbers repeat even
number of times. So we try to reduce the given problem to the simplified
problem. To do this, I have ignored the 1st occurance of any integer by
storing it into the hash table and XORing the rest of the occurances. What
this does is that, now the odd number of times occurring integers occur even
number of times and get cancelled out by the XOR operation and the only
number occuring even number of times, now gets XORed odd number of times,
resulting in the final value of sum to be the required number
Time complexity is as apparent O(n) coz adding and searching to and in a
hash table is O(1) operation.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Uwcv0-FYGjcJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
