Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

The Celebrity problem

Sharing is caring!

Problem statement
In a party of N people, only one person is known to everyone (celebrity). That celebrity doesn’t know anyone in the party. Find the celebrity if such a person exist.

Input Format
The first line of the input will contain N ( the number of people) and K. Each of the next K lines will contain 2 space separated integers i and j stating that person i knows person j.

Output Format
The person who is a celebrity.

Sample Input

4 5
1 3
2 3
4 3
2 1
1 4

Sample Output

Celebrity is 3

Solution
We will first define a helper matrix called knows[A][B] which holds true if A knows B, false otherwise. We then add all the persons to a stack and iterate over it in pairs A, B and check whether A knows B. This results in two cases:
1. If the answer is true, A can not be the celebrity, discard him.
2. If the answer is false, B can not be the celebrity, discard him.

In either case compare the probable celebrity to the next person. Each comparison should eliminate 1 person and have another as the probable celebrity. At the end we must verify that the remaining person is a celebrity.

Full code

public class FindCelebrity {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        Deque stack = new ArrayDeque();
        for (int i = 1; i <= n; i++) {
            stack.push(i);
        }

        boolean[][] knows = new boolean[n + 1][n + 1];
        for (int i = 0; i < k; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            knows[a][b] = true;
        }

        while (stack.size() > 1) {
            int a = stack.pop();
            int b = stack.pop();
            if (knows[a][b]) {
                stack.push(b);
            } else {
                stack.push(a);
            }
        }

        int candidate = stack.poll();

        // Verify that candidate is a celebrity
        for (int i = 1; i <= n; i++) {
            if (i != candidate && (!knows[i][candidate] || knows[candidate][i])) {
                System.out.println("No celebrity in party!");
                return;
            }
        }

        System.out.println("Celebrity is " + candidate);
    }
}

You can use the below Java class to generate random test cases.

public class GenerateTests {

    public static int randInt(int min, int max) {
        Random rand = new Random();
        int randomNum = rand.nextInt((max - min) + 1) + min;
        return randomNum;
    }

    public static void main(String[] args) {
        int n = 19999;
        int celebrity = randInt(1, n);

        Set<String> ans = new HashSet<String>();
        int k = 0;
        for (int i = 1; i <= n; i++) {

            // i knows celebrity
            if (i != celebrity) {
                ans.add(i + " " + celebrity);
                k++;


                // i knows 1-5 other people other than himself and celebrity
                int knows = randInt(1, 5);
                for (int j = 0; j < knows; j++) {
                    int other;
                    do {
                        other = randInt(1, n);
                    } while (other == i || other == celebrity || ans.contains(i + " " + other));

                    ans.add(i + " " + other);
                    k++;
                }
            }
        }

        System.out.println("celebrity= " + celebrity);

        try {
            PrintWriter writer = new PrintWriter(System.getProperty("user.home") + "/" + "in.txt", "UTF-8");
            writer.println(n + " " + k);
            for (String row : ans) {
                writer.println(row);
            }
            writer.close();
        } catch (IOException e) {
            // do something
        }
    }
}