I think we can assume a perfect hashing to exist. [Please correct me if I am wrong]
Implementing one, is a different issue. :)) Other than hashing, we can use BST or Heap. ~ O(klog(n)) On Thu, Jul 29, 2010 at 1:07 PM, sourav <[email protected]> wrote: > @Shiv > > Collision is itself a wel known issue in hashing and much need to be > done to avoid collision. When you say your appraoch is hash the > numbers, how do u make sure without knowing the nature of the numbers > that you can hash them without bringing ing collision of inequal items > of the array? > > > On Jul 28, 11:38 pm, "Shiv ..." <[email protected]> wrote: > > What if the number are not consecutive? > > > > My approach- > > Put the numbers in a hash till a collision occurs. > > > > On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan <[email protected] > >wrote: > > > > > > > > > Solution : > > > > > 1. Find Xor of numbers from 1 to n-1. > > > > > 2. Find Xor of the numbers present in the array. > > > > > 3. Xor the results from step 1 and 2 you will get the repeated number. > > > > > On Wed, Jul 28, 2010 at 8:46 PM, akshay <[email protected] > >wrote: > > > > >> An array of unsorted numbers n is given with one no.repeated once ie > > >> n-1 distinct nos to find duplicate no. in o(n) complexity > > > > >> -- > > >> 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]<algogeeks%[email protected]> > <algogeeks%2bunsubscr...@googlegroups.com> > > >> . > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > regards > > > > > Apoorve Mohan > > > > > -- > > > 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]<algogeeks%[email protected]> > <algogeeks%2bunsubscr...@googlegroups.com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en.- 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[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.
