Celebrity Problem

The Celebrity Problem

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

Sol:

(Using two Pointers)

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. We will find a celebrity candidate at the end of the loop. Go through each person again and check whether this is the celebrity. 

// Person with 2 is celebrity

    static int MATRIX[][] = { { 0, 0, 1, 0 },

                               { 0, 0, 1, 0 }, 

                              { 0, 0, 0, 0 },

                              { 0, 0, 1, 0 } };

  

    // Returns true if a knows

    // b, false otherwise

    static boolean knows(int a, int b) 

    {

        boolean res = (MATRIX[a][b] == 1) ? 

                                     true : 

                                     false;

        return res;

    }




int findCelebrity(int n) 

    {

        // Initialize two pointers 

        // as two corners

        int a = 0;

        int b = n - 1;

          

        // Keep moving while 

        // the two pointers

        // don't become same.

        while (a < b) 

        {

            if (knows(a, b))

                a++;

            else

                b--;

        }

  

        // Check if a is actually 

        // a celebrity or not

        for (int i = 0; i < n; i++) 

        {

            // If any person doesn't 

            // know 'a' or 'a' doesn't

            // know any person, return -1

            if (i != a && (knows(a, i) || 

                           !knows(i, a)))

                return -1;

        }

        return a;

    }




Refer here for more approaches : https://www.geeksforgeeks.org/the-celebrity-problem/