Please help me solve this problem in O(n)
Here is the question.
I can easily solve this problem in O(n^2) but I cannot solve in O(n).
There are n people. The entry K[i][j] of K[1..n][1..n] is 1 when person i knows person j and 0 otherwise. (We assume that K[i][i] = 1 for every i.) A celebrity is a person who is known by everyone and does not know anyone besides himself/herself.
We can easily prove that there is at most one celebrity in any situation. Use this ideas to construct a O(n) algorithm which finds a celebrity or concludes that there is none.
Please help me :)
Final exam is coming X))
Thank you all of you guys in advance :))
I can easily solve this problem in O(n^2) but I cannot solve in O(n).
There are n people. The entry K[i][j] of K[1..n][1..n] is 1 when person i knows person j and 0 otherwise. (We assume that K[i][i] = 1 for every i.) A celebrity is a person who is known by everyone and does not know anyone besides himself/herself.
We can easily prove that there is at most one celebrity in any situation. Use this ideas to construct a O(n) algorithm which finds a celebrity or concludes that there is none.
Please help me :)
Final exam is coming X))
Thank you all of you guys in advance :))
Topic archived. No new replies allowed.