if u know the range of values stored in array then let me assume values 1 to k then u can calculate sum of numbers stored in array in O(n) complexity. after that apply formula
duplicate value= [k*(k+1)]/2 - sum of numbers stored in array it will take O(1) constant time so total complexity becomes only O(n). it can be one solution to your problem but if the range is unknown for values then is there any solution to come in O(n)??? On 8/16/07, dsha <[EMAIL PROTECTED]> wrote: > > > Hi there, > > I'm interested in the following problem: there is an array of integers > that contains each element only once except for one element that > occurs exactly twice. Is there a way to find this element faster than > O(n*log n) and with constant extra memory? If no, how can I prove it? > > Thanks in advance for ideas. > > > > > -- Vaibhav Jain --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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 -~----------~----~----~----~------~----~------~--~---
