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
-~----------~----~----~----~------~----~------~--~---
