It can also be done in O(n) time and space with this. The XOR solution of bittusrk is interesting, too. The only advantage of this one is that it will work for any kind of object, not just numbers.
Let S be the empty set for all elements E if E is in S, remove it else add it end; for all elements E if E is not in S, print it and exit end; Implement S with a bitmap (if the numbers are "small") or a hash table. Cheers On Sep 7, 11:48 pm, Dave <dave_and_da...@juno.com> wrote: > @Sandy: It can be done in O(n) time with O(n) extra space by sorting > the data with a radix sort and then scanning the array for the element > you are seeking. > > Dave > > On Sep 7, 11:43 am, Sandy <sandy.wad...@gmail.com> wrote: > > > > > You have an array in which every number is repeated odd number of times > > except one. Write a function to find that one element in O(n) time. > > > -- > > > *Sandeep Kumar,* > > ( Mobile +91-9866507368 > > > *“I believe in smart work, Believe Me”*- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
