## [f]izzbuzzer

### 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
}
}
}```