Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

The Celebrity Problem

Medium · Stack & Queue · Asked at Amazon, Microsoft, Google, Flipkart, Zoho

M[i][j] = 1 means person i knows person j. A celebrity is known by everyone else but knows nobody. Print the celebrity's index (0-based), or -1 if there is none.

Input

First line: n. Next n lines: n values (0 or 1). M[i][i] = 0.

Output

The celebrity index, or -1.

Constraints

Eliminate candidates in pairs: if a knows b, a is not a celebrity; otherwise b is not. One candidate remains — verify it in O(n).

Example 1

Input

3
0 1 0
0 0 0
0 1 0

Output

1

Example 2

Input

2
0 1
1 0

Output

-1

Hints

  1. One question "does a know b?" always rules somebody out: if yes, a is not a celebrity; if no, b is not.
  2. After n − 1 questions one candidate is left. Check it: it must know nobody and be known by everyone.

Approach

Keep a candidate c = 0. For i = 1..n−1, if M[c][i] == 1 then c knows someone, so c = i; otherwise i is not known by c and cannot be the celebrity. Nobody else can be the celebrity, but c still might not be one — verify that M[c][i] = 0 and M[i][c] = 1 for all i ≠ c. (The same elimination works with a stack.)

Complexity: O(n) questions after reading the O(n²) matrix · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> M(n, vector<int>(n));
    for (auto &row : M)
        for (auto &x : row) cin >> x;
    int c = 0;
    for (int i = 1; i < n; i++)
        if (M[c][i]) c = i;
    for (int i = 0; i < n; i++) {
        if (i != c && (M[c][i] || !M[i][c])) {
            cout << -1 << "\n";
            return 0;
        }
    }
    cout << c << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
M = [data[1 + i * n : 1 + (i + 1) * n] for i in range(n)]
c = 0
for i in range(1, n):
    if M[c][i]:
        c = i
ok = all(i == c or (not M[c][i] and M[i][c]) for i in range(n))
print(c if ok else -1)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] M = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                in.nextToken();
                M[i][j] = (int) in.nval;
            }
        int c = 0;
        for (int i = 1; i < n; i++)
            if (M[c][i] == 1) c = i;
        for (int i = 0; i < n; i++) {
            if (i != c && (M[c][i] == 1 || M[i][c] == 0)) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(c);
    }
}

Solve The Celebrity Problem online · All practice problems