hello Dondi, in ur solution, space complexity will be O(n) in worst case. but in my solution it will constant space with linear complexity.
now think abt how to prove it if range is not known for numbers then can we achieve it or not? if not then prove it....??? On 8/17/07, Dondi Imperial <[EMAIL PROTECTED]> wrote: > > > if you know the range of the numbers don't you just have to create and > array (of length k in your example) then iterate over the array and > increment the corresponding element in the other array. > > Ie, > > int[] arrayValues = some array of a known range > int[] arrayLookup = int[min_in_range - max_in_range + 1] > > foreach(i in arrayValues) > if(arrayLookup[i] > 0) then > found > else > arrayLookup[i]++ > > Of course range could be prohibitively large (still constant though if > you know the range before hand). > > > > On 8/17/07, Vaibhav Jain <[EMAIL PROTECTED]> wrote: > > 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 > > > > > > > > > > > -- 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 -~----------~----~----~----~------~----~------~--~---
