one of the possible create the min heap O(n) keep extracting elements and look for missing elements worst case it will be O(nlgn) equivalent to heap sort
or Simply sort using quick sort or merge sort and then traverse through the array and look for missing ones On Tue, Jun 21, 2011 at 7:09 PM, keyan karthi <[email protected]>wrote: > one way might be... > find min element, max element > > declare a array buffer[max-min] > memset this to -1 > > for( i=0 to size ) > buffer[input[i]-min elemet]=1 > > now check in O(n) the first position that has a -1 in array buffer, this > position + min element is the answer.... > > but this uses lotta extra memory :( > > one easy way is to sort, run a loop from a[0] till the element not found > rite..... > > pardon me if this sounds insane !! > > > On Tue, Jun 21, 2011 at 6:39 PM, Nitish Garg <[email protected]>wrote: > >> One thing more it is not the question in which the array elements are from >> 1 to N and one element is missing. >> >> -- >> 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/-/FNbt3O17ArwJ. >> >> 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?hl=en. >> > > -- > 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?hl=en. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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?hl=en.
