Use a bit-field of M bits to keep track of the presence of X..X+M-1. We can do 2^32/M passes (if the elements are 32-bit size) to check for numbers in a range. Depending on the memory footprint and speed the app would want we can find a soft spot for X.
On Sun, Oct 4, 2009 at 9:39 PM, Amit Chandak <me.amitchan...@gmail.com>wrote: > > Hi Friends, > Given an array in which all the elements are unique except one element > which occurs 'twice'. How can we find this repeated element in O(n) > time and constant space? > > Regards, > Amit. > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---