pradeep.v.kadubandi
BAN USERThe O(n) solution where we keep them in a row and compare the current possible candidate with next person in row to eliminate either one of them or both of them as a candidate (posted by sreemana@buffalo.edu) works but with one catch.
After we do the first pass, if we are left with one possible candidate, we need to do another pass to confirm that he is indeed the celebrity. (that everyone else, to be precise, everyone else before him in the row know this person and he doesn't know any of those persons). We can return that candidate only after that check otherwise there is no celebrity.
Let me explain with an example: Let's say we have persons a,b,c,d and here are the relationships: a knows b, c knows b, b knows d, d knows a (other than these all other possible pairs are "does not know" case), in this scenario, at the end of the loop, we will have 'd' as celebrity but he is really not.
RepAayshaRosie, HTML Freshers at Abs india pvt. ltd.
Aaysha , a book editor with 4 years of experience with increasing readership and developing skilled writers. At the Daily Record ...
The O(n) solution where we keep them in a row and compare the current possible candidate with next person in row to eliminate either one of them or both of them as a candidate (posted by sreemana@buffalo.edu) works but with one catch.
- pradeep.v.kadubandi October 25, 2013After we do the first pass, if we are left with one possible candidate, we need to do another pass to confirm that he is indeed the celebrity. (that everyone else, to be precise, everyone else before him in the row know this person and he doesn't know any of those persons). We can return that candidate only after that check otherwise there is no celebrity.
Let me explain with an example: Let's say we have persons a,b,c,d and here are the relationships: a knows b, c knows b, b knows d, d knows a (other than these all other possible pairs are "does not know" case), in this scenario, at the end of the loop, we will have 'd' as celebrity but he is really not.