The Celebrity Problem Part 2

Software Development
#1

Hello Everyone,

In continuation with part 1.

We know In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.
We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise. How can we solve the problem.

Examples:

Input:
MATRIX = { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0} }
Output:id = 2
Explanation: The person with ID 2 does not
know anyone but everyone knows him

Input:
MATRIX = { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 1, 0, 0},
{0, 0, 1, 0} }
Output: No celebrity
Explanation: There is no celebrity.

Approach: The idea is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B. If A knows B, then A must not be the celebrity. Else, B must not be the celebrity. At the end of the loop, only one index will be left as a celebrity. Go through each person again and check whether this is the celebrity.
The Two Pointer approach can be used where two pointers can be assigned, one at the start and other at the end and the elements can be compared and the search space can be reduced.

Algorithm :

  1. Create two indices a and b, where a = 0 and b = n-1
  2. Run a loop until a is less than b.
  3. Check if a knows b, then a can’t be celebrity. so increment a, i.e. a++
  4. Else b cannot be celebrity, so decrement b, i.e. b–
  5. Assign a as the celebrity
  6. Run a loop from 0 to n-1 and find the count of persons who knows the celebrity and the number of people whom the celebrity knows. if the count of persons who knows the celebrity is n-1 and the count of people whom the celebrity knows is 0 then return the id of celebrity else return -1.

Implementation.

Output :

Celebrity ID 2

Complexity Analysis:

  • Time Complexity: O(n).
    Total number of comparisons 3(N-1), so the time complexity is O(n).
  • Space Complexity : O(1).
    No extra space is required.

Thankyou.