Not sure About the soln. but here goes Create a link list The node contains the number along with the list pointer. while creating the list impose a condition on insertion to chk for repetion.. i.e while traversing the list chk if the element is already inserted or not .given that n-1 are unique numbers and 1 no. repeats only , each elt will keep on being insertwed at end of the list while at the repeated element u could print the element and exit
On 8/16/06, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > Not sure about the line O(k * n) = O(n) ... > > That's probably assuming the hash-table doesn't have collision, which pretty > much is O(1). What if somehow the numbers are chosen so that a particular > hashtable would endure so many collisions, ... the complexity can then be > worst-case O(n^2) ... > > > > On 8/15/06, ridvansg <[EMAIL PROTECTED]> wrote: > > > > Hi, here is the solution. > > 1. Create a hashtable . > > 2. Go through the numbers inserting each into the hashtable. When > > insert the number check if it already exists, if so - this is the > > repeating number. > > > > The complexity: O(k*n) = O(n) > > > > > > > > > > > > > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
