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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.