Basic and Approach Using Adjacency list.
Approach :
As we are given A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j is set to 1 ( M[i][j] = 1) it means ith person knows jth person. So it is an Directed Graph we create adjacency list and check for if any adjacency list empty means the person do not know any one in party then we check if all other person in party know him then the person(i) is celebrity return index i if not then find continue.
Follow the steps below to solve the problem :
- traverse over given matrix and make adjacency list.
- make a directed edge from i to j if m[i][j]==1 in adjacency list.
- now we need to traverse over 0 to n.
- and check weather adj[i].empty() if true then check that i is present in all other adjacency list from 0 to n.
- if all other person know i then he is celebrity simply return i.
- if know one satisfy above condition retrun -1.
Below is the implementation of the above approach :
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int celebrity(vector<vector<int>>&M, int n){
// code here
vector<int>adj[n+1];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(M[i][j]==1){
adj[i].push_back(j);
}
}
}
vector<int>::iterator it;
for(int i=0;i<n;i++){
if(adj[i].empty()){
bool flag=1;
for(int j=0;j<n;j++){
if(i==j)continue;
it=find(adj[j].begin(),adj[j].end(),i);
if(it==adj[j].end()){
flag=0;
break;
}
}
if(flag)return i;
}
}
return -1;
}
int main() {
vector<vector<int>>M{ {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0} };
int n=M.size();
int Celebrity=celebrity(M,n);
if(Celebrity!=-1){
cout<<"Celebrity is : "<<Celebrity<<endl;
}else{
cout<<"No celebrity"<<endl;
}
//Code and Approach Contributed By Sanket Gode.
return 0;
}
import java.util.*;
public class Main {
public static int celebrity(ArrayList<ArrayList<Integer>> M, int n) {
ArrayList<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
for (int j = 0; j < n; j++) {
if (M.get(i).get(j) == 1) {
adj[i].add(j);
}
}
}
for (int i = 0; i < n; i++) {
if (adj[i].isEmpty()) {
boolean flag = true;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (!adj[j].contains(i)) {
flag = false;
break;
}
}
if (flag)
return i;
}
}
return -1;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> M = new ArrayList<>();
M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));
M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));
M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));
int n = M.size();
int Celebrity = celebrity(M, n);
if (Celebrity != -1) {
System.out.println("Celebrity is : " + Celebrity);
} else {
System.out.println("No celebrity");
}
}
}
def celebrity(M, n):
# Create an adjacency list for each person
adj = [[] for i in range(n)]
for i in range(n):
for j in range(n):
if M[i][j] == 1:
adj[i].append(j)
# Check if there is a person
# who doesn't know anyone but
# everyone knows him/her
for i in range(n):
if not adj[i]:
flag = True
for j in range(n):
if i == j:
continue
if i not in adj[j]:
flag = False
break
if flag:
return i
return -1
# Sample input
M = [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0]]
n = len(M)
Celebrity = celebrity(M, n)
if Celebrity != -1:
print("Celebrity is : ", Celebrity)
else:
print("No celebrity")
using System;
using System.Collections.Generic;
public class MainClass {
public static int Celebrity(List<List<int> > M, int n)
{
List<int>[] adj = new List<int>[ n ];
for (int i = 0; i < n; i++) {
adj[i] = new List<int>();
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
adj[i].Add(j);
}
}
}
for (int i = 0; i < n; i++) {
if (adj[i].Count == 0) {
bool flag = true;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (!adj[j].Contains(i)) {
flag = false;
break;
}
}
if (flag)
return i;
}
}
return -1;
}
public static void Main(string[] args)
{
List<List<int> > M = new List<List<int> >{
new List<int>{ 0, 0, 1, 0 },
new List<int>{ 0, 0, 1, 0 },
new List<int>{ 0, 0, 0, 0 },
new List<int>{ 0, 0, 1, 0 }
};
int n = M.Count;
int CelebrityResult = Celebrity(M, n);
if (CelebrityResult != -1) {
Console.WriteLine("Celebrity is : "
+ CelebrityResult);
}
else {
Console.WriteLine("No celebrity");
}
}
}
// Javascript code addition
function celebrity(M) {
const n = M.length;
// Create an adjacency list for each person
const adj = [];
for (let i = 0; i < n; i++) {
adj[i] = [];
for (let j = 0; j < n; j++) {
if (M[i][j] === 1) {
adj[i].push(j);
}
}
}
// Check if there is a person
// who doesn't know anyone but
// everyone knows him/her
for (let i = 0; i < n; i++) {
if (adj[i].length === 0) {
let flag = true;
for (let j = 0; j < n; j++) {
if (i === j) continue;
if (!adj[j].includes(i)) {
flag = false;
break;
}
}
if (flag) return i;
}
}
return -1;
}
// Sample input
const M = [
[0, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 1, 0]
];
const Celebrity = celebrity(M);
if (Celebrity !== -1) {
console.log("Celebrity is: " + Celebrity);
} else {
console.log("No celebrity");
}
// The code is contributed by Arushi Goel.
Output
Celebrity is : 2
Complexity Analysis :
Time Complexity: O(N^2)
Auxiliary Space: O(N)
The Celebrity Problem
In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at 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, and 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 himInput:
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.