i think it will not perform good, if you have cards like this 1 2 3 4 5 5 5 5 the supposed solution is, keep one counter and one candidate first , the candidate is the first element, and counter is 1 if the next card equals candidate increase the count to 1, else decrease it if counter is zero you must take the new value as candidate, i am not sure if you do this before decreasing. I am only telling you what i remember from lecture. And at the and cehck if the candidate is correct. And it can be proven that if there is more than n/2 same cards the candidate will be one of them
2008/12/11 Geoffrey Summerhayes <[email protected]> > > > > On Dec 9, 2:22 pm, Tower <[email protected]> wrote: > > A bank has a collection of n bank cards that they've confiscated, > > suspecting them of being used in a fraud. Each bank card corresponds > > to a unique account in the bank. Each account can have many cards > > corresponding to it, and we'll say that two bank cards are equivalent > > if they correspond to the same account. The only way to say 2 cards > > are equivalent is by using a high-tech "equivalence-tester" that takes > > in 2 cards, and after performing some computations, determines whether > > they are equivalent. > > Their question is the following: among the collection of n cards, is > > there a set of more than n/2 of them that are all equivalent to one > > another? Assume that the only feasible operations you can do with the > > cards are to pick two of them and plug them in to the equivalence > > tester. > > Best I can come up with is a list of a card + count that is sorted > by count, largest first. If the number of remaining cards + the count > of the head of the list is <= n/2 return false. Otherwise, check the > next > card against each member in the list. If a match is found, increment > the count, if count>n/2 return true, else check to see if the entry > needs > repositioning. If the card doesn't match any group create a new entry > at the end of the list containing the card with the count set to one. > > Not sure what the worst case is, but it should perform reasonably. > > -- > Geoff > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
