A party N people，if the one does not know all others，and is known by all others，this person is called celebrity. O(n) time to find celebrity.
1. Ask a if he knows b, if a knows b, a is not celebrity, if not, b is not
celebrity, if a,b knows each other or a ,b does not know each other, both of them are not celebrity. after asking (n-1) questions, one person called CP left.
2. Ask CP (n-1) questions, if he knows all the other n-1 persons. If yes, no
celebrity. otherwise
3. Check (n-2) persons if they all knows CP.
So total # of questions in worst case is 3n-4
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment