En un grupo de N personas, solo una persona es conocida por todos. Tal persona puede estar presente en la fiesta, si es así, no conoce a nadie en la fiesta. Solo podemos hacer preguntas como “ ¿A conoce a B? “. Encuentra al extraño (celebridad) en el mínimo número de preguntas.
Podemos describir la entrada del problema como una array de números/caracteres que representan a las personas del grupo. También tenemos una función hipotética HaveAcquaintance(A, B) que devuelve verdadero si A conoce a B, falso en caso contrario. Cómo podemos resolver el problema.
Ejemplos:
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 him
Input:
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.
Medimos la complejidad en términos de llamadas realizadas a HaveAcquaintance().
Método 1: Utiliza Graph para llegar a la solución particular.
Enfoque:
Modele la solución usando gráficos. Inicialice el grado interior y exterior de cada vértice como 0. Si A conoce B, dibuje una arista dirigida de A a B, aumente el grado interior de B y el grado exterior de A en 1. Construya todas las aristas posibles del gráfico para cada par posible [i, j ]. Hay NC pares C2 . Si una celebridad está presente en la fiesta, habrá un Node sumidero en el gráfico con un grado de salida de cero y un grado de entrada de N-1.
Algoritmo:
- Cree dos arrays de grado interior y exterior , para almacenar el grado interior y exterior
- Ejecute un bucle anidado, el bucle exterior de 0 a n y el bucle interior de 0 a n.
- Para cada par i, j verifique si conozco j y luego aumente el grado exterior de i y el grado interior de j
- Para cada par i, j comprueba si j sabe que i luego aumenta el grado exterior de j y el grado interior de i
- Ejecute un ciclo de 0 a n y encuentre la identificación donde el grado de entrada es n-1 y el grado de salida es 0
Implementación:
C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;
// Max # of persons in the party
#define N 8
// Person with 2 is celebrity
bool MATRIX[N][N] = {{0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0}};
bool knows(int a, int b)
{
return MATRIX[a][b];
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
int findCelebrity(int n)
{
//the graph needs not be constructed
//as the edges can be found by
//using knows function
//degree array;
int indegree[n]={0},outdegree[n]={0};
//query for all edges
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
int x = knows(i,j);
//set the degrees
outdegree[i]+=x;
indegree[j]+=x;
}
}
//find a person with indegree n-1
//and out degree 0
for(int i=0; i<n; i++)
if(indegree[i] == n-1 && outdegree[i] == 0)
return i;
return -1;
}
// Driver code
int main()
{
int n = 4;
int id = findCelebrity(n);
id == -1 ? cout << "No celebrity" :
cout << "Celebrity ID " << id;
return 0;
}
Java
// Java program to find celebrity
import java.util.*;
class GFG {
// Max # of persons in the party
static final int N = 8;
// Person with 2 is celebrity
static int MATRIX[][] = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
static int knows(int a, int b) { return MATRIX[a][b]; }
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
static int findCelebrity(int n)
{
// the graph needs not be constructed
// as the edges can be found by
// using knows function
// degree array;
int[] indegree = new int[n];
int[] outdegree = new int[n];
// query for all edges
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int x = knows(i, j);
// set the degrees
outdegree[i] += x;
indegree[j] += x;
}
}
// find a person with indegree n-1
// and out degree 0
for (int i = 0; i < n; i++)
if (indegree[i] == n - 1 && outdegree[i] == 0)
return i;
return -1;
}
// Driver code
public static void main(String[] args)
{
int n = 4;
int id = findCelebrity(n);
if (id == -1)
System.out.print("No celebrity");
else
System.out.print("Celebrity ID " + id);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find celebrity
# Max # of persons in the party
N = 8
# Person with 2 is celebrity
MATRIX = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ]
def knows(a, b):
return MATRIX[a][b]
def findCelebrity(n):
# The graph needs not be constructed
# as the edges can be found by
# using knows function
# degree array;
indegree = [0 for x in range(n)]
outdegree = [0 for x in range(n)]
# Query for all edges
for i in range(n):
for j in range(n):
x = knows(i, j)
# Set the degrees
outdegree[i] += x
indegree[j] += x
# Find a person with indegree n-1
# and out degree 0
for i in range(n):
if (indegree[i] == n - 1 and
outdegree[i] == 0):
return i
return -1
# Driver code
if __name__ == '__main__':
n = 4
id_ = findCelebrity(n)
if id_ == -1:
print("No celebrity")
else:
print("Celebrity ID", id_)
# This code is contributed by UnworthyProgrammer
C#
// C# program to find celebrity
using System;
public class GFG
{
// Max # of persons in the party
static readonly int N = 8;
// Person with 2 is celebrity
static int[,] MATRIX = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
static int knows(int a, int b) { return MATRIX[a,b]; }
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
static int findCelebrity(int n)
{
// the graph needs not be constructed
// as the edges can be found by
// using knows function
// degree array;
int[] indegree = new int[n];
int[] outdegree = new int[n];
// query for all edges
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int x = knows(i, j);
// set the degrees
outdegree[i] += x;
indegree[j] += x;
}
}
// find a person with indegree n-1
// and out degree 0
for (int i = 0; i < n; i++)
if (indegree[i] == n - 1 && outdegree[i] == 0)
return i;
return -1;
}
// Driver code
public static void Main(String[] args)
{
int n = 4;
int id = findCelebrity(n);
if (id == -1)
Console.Write("No celebrity");
else
Console.Write("Celebrity ID " + id);
}
}
// This code is contributed by aashish1995
Javascript
<script>
// JavaScript program to find celebrity
// Max # of persons in the party
var N = 8;
// Person with 2 is celebrity
var MATRIX = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ];
function knows(a , b) {
return MATRIX[a][b];
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
function findCelebrity(n) {
// the graph needs not be constructed
// as the edges can be found by
// using knows function
// degree array;
var indegree = Array(n).fill(0);
var outdegree = Array(n).fill(0);
// query for all edges
for (var i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
var x = knows(i, j);
// set the degrees
outdegree[i] += x;
indegree[j] += x;
}
}
// find a person with indegree n-1
// and out degree 0
for (i = 0; i < n; i++)
if (indegree[i] == n - 1 && outdegree[i] == 0)
return i;
return -1;
}
// Driver code
var n = 4;
var id = findCelebrity(n);
if (id == -1)
document.write("No celebrity");
else
document.write("Celebrity ID " + id);
// This code is contributed by todaysgaurav
</script>
Producción
Celebrity ID 2
Análisis de Complejidad:
- Complejidad Temporal: O(n 2 ).
Se ejecuta un bucle anidado atravesando la array, por lo que la complejidad del tiempo es O (n 2 ) - Complejidad espacial: O(n).
Dado que se requiere espacio adicional de tamaño n.
Método 2: utiliza la recursividad
Enfoque:
El problema se puede resolver usando recursividad. Digamos, si se conoce la ‘celebridad potencial’ de las personas N-1, ¿se puede encontrar la solución para N a partir de ella? Una celebridad potencial es aquella que es la única que queda después de eliminar a n-1 personas. Se eliminan n-1 personas con la siguiente estrategia:
- Si A conoce a B, entonces A no puede ser una celebridad. Pero B podría ser.
- De lo contrario, si B conoce a A, entonces B no puede ser una celebridad. Pero A podría ser.
El enfoque mencionado anteriormente usa Recursion para encontrar la celebridad potencial entre n personas, llama recursivamente a n-1 personas, hasta que se alcanza el caso base de 0 personas. Para 0 personas se devuelve -1 indicando que no hay posibles celebridades ya que hay 0 personas. En la i-ésima etapa de recursividad, la i-ésima persona y la (i-1)-ésima persona se comparan para comprobar si alguna de ellas conoce a la otra. Y utilizando la lógica anterior (en las viñetas), la celebridad potencial vuelve a la etapa (i+1).
Una vez que la función recursiva devuelve un id. Verificamos si esta identificación no conoce a nadie más, pero todos los demás conocen esta identificación. Si esto es cierto, entonces esta identificación será la celebridad.
Algoritmo:
- Cree una función recursiva que tome un número entero n.
- Compruebe el caso base, si el valor de n es 0, devuelva -1.
- Llame a la función recursiva y obtenga la identificación de la celebridad potencial de los primeros n-1 elementos.
- Si la identificación es -1, asigne n como la celebridad potencial y devuelva el valor.
- Si la celebridad potencial de los primeros n-1 elementos conoce n-1, devuelve n-1, (indexación basada en 0)
- Si la celebridad de los primeros n-1 elementos no conoce n-1, devuelva la identificación de la celebridad de los n-1 elementos (indexación basada en 0)
- De lo contrario, devuelve -1
- Cree una función contenedora y verifique si la identificación devuelta por la función es realmente la celebridad o no.
Implementación:
C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;
// Max # of persons in the party
#define N 8
// Person with 2 is celebrity
bool MATRIX[N][N] = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
bool knows(int a, int b) { return MATRIX[a][b]; }
// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
int findPotentialCelebrity(int n)
{
// base case - when n reaches 0 , returns -1
// since n represents the number of people,
// 0 people implies no celebrity(= -1)
if (n == 0)
return -1;
// find the celebrity with n-1
// persons
int id = findPotentialCelebrity(n - 1);
// if there are no celebrities
if (id == -1)
return n - 1;
// if the id knows the nth person
// then the id cannot be a celebrity, but nth person
// could be one
else if (knows(id, n - 1)) {
return n - 1;
}
// if the nth person knows the id,
// then the nth person cannot be a celebrity and the id
// could be one
else if (knows(n - 1, id)) {
return id;
}
// if there is no celebrity
return -1;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
int Celebrity(int n)
{
// find the celebrity
int id = findPotentialCelebrity(n);
// check if the celebrity found
// is really the celebrity
if (id == -1)
return id;
else {
int c1 = 0, c2 = 0;
// check the id is really the
// celebrity
for (int i = 0; i < n; i++)
if (i != id) {
c1 += knows(id, i);
c2 += knows(i, id);
}
// if the person is known to
// everyone.
if (c1 == 0 && c2 == n - 1)
return id;
return -1;
}
}
// Driver code
int main()
{
int n = 4;
int id = Celebrity(n);
id == -1 ? cout << "No celebrity"
: cout << "Celebrity ID " << id;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Max # of persons in the party
static int N = 8;
// Person with 2 is celebrity
static int MATRIX[][] = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
static int knows(int a, int b) { return MATRIX[a][b]; }
// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
static int findPotentialCelebrity(int n)
{
// base case - when n reaches 0 , returns -1
// since n represents the number of people,
// 0 people implies no celebrity(= -1)
if (n == 0)
return -1;
// find the celebrity with n-1
// persons
int id = findPotentialCelebrity(n - 1);
// if there are no celebrities
if (id == -1)
return n - 1;
// if the id knows the nth person
// then the id cannot be a celebrity, but nth person
// could be one
else if (knows(id, n - 1) == 1) {
return n - 1;
}
// if the nth person knows the id,
// then the nth person cannot be a celebrity and the
// id could be one
else if (knows(n - 1, id) == 1) {
return id;
}
// if there is no celebrity
return -1;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
static int Celebrity(int n)
{
// find the celebrity
int id = findPotentialCelebrity(n);
// check if the celebrity found
// is really the celebrity
if (id == -1)
return id;
else {
int c1 = 0, c2 = 0;
// check the id is really the
// celebrity
for (int i = 0; i < n; i++)
if (i != id) {
c1 += knows(id, i);
c2 += knows(i, id);
}
// if the person is known to
// everyone.
if (c1 == 0 && c2 == n - 1)
return id;
return -1;
}
}
// Driver code
public static void main(String[] args)
{
int n = 4;
int id = Celebrity(n);
if (id == -1) {
System.out.println("No celebrity");
}
else {
System.out.println("Celebrity ID " + id);
}
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program to find celebrity
# Max # of persons in the party
N = 8
# Person with 2 is celebrity
MATRIX = [[0, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 1, 0]]
def knows(a, b):
return MATRIX[a][b]
# Returns -1 if a potential celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
def findPotentialCelebrity(n):
# Base case
if (n == 0):
return 0;
# Find the celebrity with n-1
# persons
id_ = findPotentialCelebrity(n - 1)
# If there are no celebrities
if (id_ == -1):
return n - 1
# if the id knows the nth person
# then the id cannot be a celebrity, but nth person
# could be on
elif knows(id_, n - 1):
return n - 1
# if the id knows the nth person
# then the id cannot be a celebrity, but nth person
# could be one
elif knows(n - 1, id_):
return id_
# If there is no celebrity
return - 1
# Returns -1 if celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
# a wrapper over findCelebrity
def Celebrity(n):
# Find the celebrity
id_=findPotentialCelebrity(n)
# Check if the celebrity found
# is really the celebrity
if (id_ == -1):
return id_
else:
c1=0
c2=0
# Check the id is really the
# celebrity
for i in range(n):
if (i != id_):
c1 += knows(id_, i)
c2 += knows(i, id_)
# If the person is known to
# everyone.
if (c1 == 0 and c2 == n - 1):
return id_
return -1
# Driver code
if __name__ == '__main__':
n=4
id_=Celebrity(n)
if id_ == -1:
print("No celebrity")
else:
print("Celebrity ID", id_)
# This code is contributed by UnworthyProgrammer
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Max # of persons in the party
static int N = 8;
// Person with 2 is celebrity
static int [,]MATRIX = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
static int knows(int a, int b) { return MATRIX[a,b]; }
// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
static int findPotentialCelebrity(int n)
{
// base case - when n reaches 0 , returns -1
// since n represents the number of people,
// 0 people implies no celebrity(= -1)
if (n == 0)
return -1;
// find the celebrity with n-1
// persons
int id = findPotentialCelebrity(n - 1);
// if there are no celebrities
if (id == -1)
return n - 1;
// if the id knows the nth person
// then the id cannot be a celebrity, but nth person
// could be one
else if (knows(id, n - 1) == 1) {
return n - 1;
}
// if the nth person knows the id,
// then the nth person cannot be a celebrity and the
// id could be one
else if (knows(n - 1, id) == 1) {
return id;
}
// if there is no celebrity
return -1;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
static int Celebrity(int n)
{
// find the celebrity
int id = findPotentialCelebrity(n);
// check if the celebrity found
// is really the celebrity
if (id == -1)
return id;
else {
int c1 = 0, c2 = 0;
// check the id is really the
// celebrity
for (int i = 0; i < n; i++)
if (i != id) {
c1 += knows(id, i);
c2 += knows(i, id);
}
// if the person is known to
// everyone.
if (c1 == 0 && c2 == n - 1)
return id;
return -1;
}
}
// Driver code
public static void Main(String[] args)
{
int n = 4;
int id = Celebrity(n);
if (id == -1) {
Console.WriteLine("No celebrity");
}
else {
Console.WriteLine("Celebrity ID " + id);
}
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Max # of persons in the party
var N = 8;
// Person with 2 is celebrity
var MATRIX = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ];
function knows(a, b)
{
return MATRIX[a][b];
}
// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
function findPotentialCelebrity(n)
{
// base case - when n reaches 0 , returns -1
// since n represents the number of people,
// 0 people implies no celebrity(= -1)
if (n == 0)
return -1;
// find the celebrity with n-1
// persons
var id = findPotentialCelebrity(n - 1);
// if there are no celebrities
if (id == -1)
return n - 1;
// if the id knows the nth person
// then the id cannot be a celebrity, but nth person
// could be one
else if (knows(id, n - 1) == 1) {
return n - 1;
}
// if the nth person knows the id,
// then the nth person cannot be a celebrity and the
// id could be one
else if (knows(n - 1, id) == 1) {
return id;
}
// if there is no celebrity
return -1;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
function Celebrity(n)
{
// find the celebrity
var id = findPotentialCelebrity(n);
// check if the celebrity found
// is really the celebrity
if (id == -1)
return id;
else {
var c1 = 0, c2 = 0;
// check the id is really the
// celebrity
for (var i = 0; i < n; i++)
if (i != id) {
c1 += knows(id, i);
c2 += knows(i, id);
}
// if the person is known to
// everyone.
if (c1 == 0 && c2 == n - 1)
return id;
return -1;
}
}
// Driver code
var n = 4;
var id = Celebrity(n);
if (id == -1) {
document.write("No celebrity");
}
else {
document.write("Celebrity ID " + id);
}
// This code is contributed by shivanisinghss2110
</script>
Producción
Celebrity ID 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
La función recursiva se llama n veces, por lo que la complejidad temporal es O(n). - Complejidad espacial: O(1).
Como no se requiere espacio adicional.
Método 3: Utiliza la técnica de eliminación
Enfoque: Hay algunas observaciones basadas en la técnica de eliminación (consulte el libro Cómo resolverlo de Polya ).
- Si A conoce a B, entonces A no puede ser una celebridad. Deseche A, y B puede ser una celebridad .
- Si A no conoce a B, entonces B no puede ser una celebridad. Deseche B, y A puede ser una celebridad .
- Repita los dos pasos anteriores hasta que solo haya una persona.
- Asegúrese de que la persona restante sea una celebridad. (¿Cuál es la necesidad de este paso?)
Algoritmo:
- Cree una pila y empuje todas las identificaciones en la pila.
- Ejecute un ciclo mientras haya más de 1 elemento en la pila.
- Extraiga los dos elementos superiores de la pila (representarlos como A y B)
- Si A conoce a B, entonces A no puede ser una celebridad y empujar a B en la pila. De lo contrario, si A no conoce a B, entonces B no puede ser una celebridad empujando a A en la pila.
- Asigne el elemento restante en la pila como la celebridad.
- Ejecute un ciclo de 0 a n-1 y encuentre la cantidad de personas que conocen a la celebridad y la cantidad de personas que la celebridad conoce. si la cantidad de personas que conocen a la celebridad es n-1 y la cantidad de personas que la celebridad conoce es 0, devuelva la identificación de la celebridad; de lo contrario, devuelva -1.
Implementación:
C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;
// Max # of persons in the party
#define N 8
// Person with 2 is celebrity
bool MATRIX[N][N] = {{0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0}};
bool knows(int a, int b)
{
return MATRIX[a][b];
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
int findCelebrity(int n)
{
stack<int> s;
// Celebrity
int C;
// Push everybody to stack
for (int i = 0; i < n; i++)
s.push(i);
// Extract top 2
// Find a potential celebrity
while (s.size() > 1)
{ int A = s.top();
s.pop();
int B = s.top();
s.pop();
if (knows(A, B))
{
s.push(B);
}
else
{
s.push(A);
}
}
// Potential candidate?
C = s.top();
s.pop();
// Check if C is actually
// a celebrity or not
for (int i = 0; i < n; i++)
{
// If any person doesn't
// know 'C' or 'C' doesn't
// know any person, return -1
if ( (i != C) &&
(knows(C, i) ||
!knows(i, C)) )
return -1;
}
return C;
}
// Driver code
int main()
{
int n = 4;
int id = findCelebrity(n);
id == -1 ? cout << "No celebrity" :
cout << "Celebrity ID " << id;
return 0;
}
Java
// Java program to find celebrity using
// stack data structure
import java.util.Stack;
class GFG
{
// 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;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
static int findCelebrity(int n)
{
Stack<Integer> st = new Stack<>();
int c;
// Step 1 :Push everybody
// onto stack
for (int i = 0; i < n; i++)
{
st.push(i);
}
while (st.size() > 1)
{
// Step 2 :Pop off top
// two persons from the
// stack, discard one
// person based on return
// status of knows(A, B).
int a = st.pop();
int b = st.pop();
// Step 3 : Push the
// remained person onto stack.
if (knows(a, b))
{
st.push(b);
}
else
st.push(a);
}
// If there are only two people
// and there is no
// potential candidate
if(st.empty())
return -1;
c = st.pop();
// Step 5 : Check if the last
// person is celebrity or not
for (int i = 0; i < n; i++)
{
// If any person doesn't
// know 'c' or 'a' doesn't
// know any person, return -1
if (i != c && (knows(c, i) ||
!knows(i, c)))
return -1;
}
return c;
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
int result = findCelebrity(n);
if (result == -1)
{
System.out.println("No Celebrity");
}
else
System.out.println("Celebrity ID " +
result);
}
}
// This code is contributed
// by Rishabh Mahrsee
Python3
# Python3 program to find celebrity
# using stack data structure
# Max # of persons in the party
N = 8
# Person with 2 is celebrity
MATRIX = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ]
def knows(a, b):
return MATRIX[a][b]
# Returns -1 if celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
def findCelebrity(n):
# Handle trivial
# case of size = 2
s = []
# Push everybody to stack
for i in range(n):
s.append(i)
# Find a potential celebrity
while (len(s) > 1):
# Pop out the first two elements from stack
A = s.pop()
B = s.pop()
# if A knows B, we find that B might be the celebrity and vice versa
if (knows(A, B)):
s.append(B)
else:
s.append(A)
# If there are only two people
# and there is no
# potential candidate
if(len(s) == 0):
return -1
# Potential candidate?
C = s.pop();
# Last candidate was not
# examined, it leads one
# excess comparison (optimize)
if (knows(C, B)):
C = B
if (knows(C, A)):
C = A
# Check if C is actually
# a celebrity or not
for i in range(n):
# If any person doesn't
# know 'a' or 'a' doesn't
# know any person, return -1
if ((i != C) and
(knows(C, i) or
not(knows(i, C)))):
return -1
return C
# Driver code
if __name__ == '__main__':
n = 4
id_ = findCelebrity(n)
if id_ == -1:
print("No celebrity")
else:
print("Celebrity ID ", id_)
# This code is contributed by UnworthyProgrammer
C#
// C# program to find celebrity using
// stack data structure
using System;
using System.Collections.Generic;
public class GFG
{
// 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 bool knows(int a, int b)
{
bool res = (MATRIX[a,b] == 1) ?
true :
false;
return res;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
static int findCelebrity(int n)
{
Stack<int> st = new Stack<int>();
int c;
// Step 1 :Push everybody
// onto stack
for (int i = 0; i < n; i++)
{
st.Push(i);
}
while (st.Count > 1)
{
// Step 2 :Pop off top
// two persons from the
// stack, discard one
// person based on return
// status of knows(A, B).
int a = st.Pop();
int b = st.Pop();
// Step 3 : Push the
// remained person onto stack.
if (knows(a, b))
{
st.Push(b);
}
else
st.Push(a);
}
// If there are only two people
// and there is no
// potential candidate
if(st.Count==0)
return -1;
c = st.Pop();
// Step 5 : Check if the last
// person is celebrity or not
for (int i = 0; i < n; i++)
{
// If any person doesn't
// know 'c' or 'a' doesn't
// know any person, return -1
if (i != c && (knows(c, i) ||
!knows(i, c)))
return -1;
}
return c;
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
int result = findCelebrity(n);
if (result == -1)
{
Console.WriteLine("No Celebrity");
}
else
Console.WriteLine("Celebrity ID " +
result);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to find celebrity using
// stack data structure
// Person with 2 is celebrity
var 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
function knows(a , b) {
var res = (MATRIX[a][b] == 1) ? true : false;
return res;
}
// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
function findCelebrity(n) {
var st = new Array();
var c;
// Step 1 :Push everybody
// onto stack
for (var i = 0; i < n; i++) {
st.push(i);
}
while (st.length > 1)
{
// Step 2 :Pop off top
// two persons from the
// stack, discard one
// person based on return
// status of knows(A, B).
var a = st.pop();
var b = st.pop();
// Step 3 : Push the
// remained person onto stack.
if (knows(a, b)) {
st.push(b);
}
else
st.push(a);
}
// If there are only two people
// and there is no
// potential candidate
if (st.length==0)
return -1;
c = st.pop();
// Step 5 : Check if the last
// person is celebrity or not
for (i = 0; i < n; i++)
{
// If any person doesn't
// know 'c' or 'a' doesn't
// know any person, return -1
if (i != c && (knows(c, i) || !knows(i, c)))
return -1;
}
return c;
}
// Driver Code
var n = 4;
var result = findCelebrity(n);
if (result == -1) {
document.write("No Celebrity");
} else
document.write("Celebrity ID " + result);
// This code is contributed by gauravrajput1
</script>
Producción
Celebrity ID 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
El número total de comparaciones 3(N-1), por lo que la complejidad temporal es O(n). - Complejidad espacial: O(n).
Se necesita espacio adicional para almacenar la pila.
Enfoque: similar al enfoque anterior, seguiremos estos 2 pasos
- Si A conoce a B, entonces A no puede ser una celebridad. Descarte A, y B puede ser una celebridad.
- Si A no conoce a B, entonces B no puede ser una celebridad. Deseche B, y A puede ser una celebridad.
No usaremos ningún espacio adicional, ya que usaremos espacios M[i][i] para almacenar si la i-ésima persona es una celebridad o no, ya que por defecto son 0, por lo que si encontramos que la i-ésima persona no es una celebridad, lo haremos marcar M[i][i] como 1
Algoritmo:
- Crearemos una variable que almacenará la fila actual e iniciará un ciclo de 0 a n-1 y si M[fila][i] es 1, entonces marque M[fila][fila]=1 y actualice fila = i y si M[fila][i]=0 luego marque M[i][i]=1.
- Después del ciclo, iteramos en la diagonal de la array, es decir, M[i][i] donde i->(0,n-1) habrá solo un elemento en la diagonal cuyo valor será 0, cuando se encuentre iterar en todos las filas de arriba a abajo con la columna establecida en i y si no hay 0 en esa columna, devuelva i y si hay un número positivo de ceros, devuelva -1
Implementación:
C++
#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
//Function to find if there is a celebrity in the party or not.
int celebrity(int M[4][4], int n)
{
// r=row number
int r=0;
for (int i=1;i<n;i++)
{
//checking if r th person knows i th person
if (M[r][i]==1)
{
M[r][r]=1;
r=i;
}
else
{
M[i][i]=1;
}
}
for (int i=0;i<n;i++)
{
// checking if i th person can be a celebrity or not
if (M[i][i]==0)
{
int flag=0;
// iterating in the i th column to check
// whether everyone knows i th person or not
for (int j=0;j<n;j++)
{
// checking if M[j][i] is not a diagonal element
// and if j th person knows i th person
if (j!=i && M[j][i]==0)
{
flag=1;
break;
}
}
if (flag==0)
return i;
}
}
return -1;
}
};
int main()
{
int M[4][4]={{0,0,1,0},
{0,0,1,0},
{0,0,0,0},
{0,0,1,0}};
Solution ob;
int a=ob.celebrity(M,4);
if (a==-1)
{
cout<<"No Celebrity Present"<<endl;
}
else
{
cout<<"Celebrity ID "<<a<<endl;
}
}
// Contributed by Yash Goyal
Producción
Celebrity ID 2
Análisis de Complejidad:
- Complejidad de tiempo: O(n)
- El número de iteraciones es 3 veces, es decir, 3n, por lo que la complejidad del tiempo es O(n)
- Complejidad espacial: O(1)
- No se requiere espacio adicional
Método 4: utiliza un enfoque de dos puntos
Enfoque óptimo: la idea es usar dos punteros, uno desde el principio y otro desde el final. Suponga que la persona inicial es A y la persona final es B. Si A conoce a B, entonces A no debe ser la celebridad. De lo contrario, B no debe ser la celebridad. Al final del ciclo, solo quedará un índice como celebridad. Revise a cada persona nuevamente y verifique si se trata de la celebridad.
El enfoque de dos punteros se puede utilizar cuando se pueden asignar dos punteros, uno al principio y otro al final, y los elementos se pueden comparar y el espacio de búsqueda se puede reducir.
Algoritmo:
- Cree dos índices i y j, donde i = 0 y j = n-1
- Ejecute un ciclo hasta que i sea menor que j.
- Comprueba si conozco a j, entonces no puedo ser una celebridad. entonces incrementa i, es decir, i++
- De lo contrario, j no puede ser una celebridad, por lo tanto, disminuya j, es decir, j–
- Asignar i como candidato a celebridad
- Ahora, por fin, verifique si el candidato es realmente una celebridad volviendo a ejecutar un ciclo de 0 a n-1 y verificando constantemente que si el candidato conoce a una persona o si hay un candidato que no conoce al candidato, entonces deberíamos devolver -1. de lo contrario, al final del ciclo, podemos estar seguros de que el candidato es en realidad una celebridad.
Implementación:
Java
// Java program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
import java.io.*;
class GFG {
public static void main(String[] args)
{
int[][] M = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
System.out.println("No celebrity found!");
else {
System.out.println(
"0-based celebrity index is : " + celebIdx);
}
}
public static int celebrity(int M[][], int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // j doesnt know i so i cant be celebrity
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
}
Python3
# Python3 code
class Solution:
# Function to find if there is a celebrity in the party or not.
# return index if celebrity else return -1
def celebrity(self, M, n):
# code here
i = 0
j = n-1
candidate = -1
while(i < j):
if M[j][i] == 1:
j -= 1
else:
i += 1
candidate = i
for k in range(n):
if candidate != k:
if M[candidate][k] == 1 or M[k][candidate] == 0:
return -1
return candidate
n = 4
m = [[0, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 1, 0]]
ob = Solution()
print("Celebrity at index "+str(ob.celebrity(m, n)))
C#
// C# program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
using System;
class GFG {
public static void Main(String[] args)
{
int[,] M = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
Console.Write("No celebrity found!");
else {
Console.Write(
"0-based celebrity index is : " + celebIdx);
}
}
public static int celebrity(int [,]M, int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j,i] == 1) // j knows i
j--;
else // i knows j
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i,candidate] == 0
|| M[candidate,i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
var M = [ [ 0, 0, 1, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ];
var celebIdx = celebrity(M, 4);
if (celebIdx == -1)
document.write("No celebrity found!");
else {
document.write(
"0-based celebrity index is : " + celebIdx);
}
function celebrity( M, n)
{
// This function returns the celebrity
// index 0-based (if any)
var i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // i knows j
i++;
}
// i points to our celebrity candidate
var candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
// This code is contributed by shivanisinghss2110
</script>
C++
// C++ program to find celebrity
// in the given Matrix of people
#include<bits/stdc++.h>
using namespace std;
#define N 4
int celebrity(int M[N][N], int n)
{
// This function returns the celebrity
// index 0-based (if any)
int i = 0, j = n - 1;
while (i < j) {
if (M[j][i] == 1) // j knows i
j--;
else // j doesnt know i so i cant be celebrity
i++;
}
// i points to our celebrity candidate
int candidate = i;
// Now, all that is left is to check that whether
// the candidate is actually a celebrity i.e: he is
// known by everyone but he knows no one
for (i = 0; i < n; i++) {
if (i != candidate) {
if (M[i][candidate] == 0
|| M[candidate][i] == 1)
return -1;
}
}
// if we reach here this means that the candidate
// is really a celebrity
return candidate;
}
int main()
{
int M[N][N] = { { 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 0 } };
int celebIdx = celebrity(M, 4);
if (celebIdx == -1)
cout<<("No celebrity found!");
else {
cout<<
"0-based celebrity index is : " << celebIdx;
}
return 0;
}
// This code contributed by gauravrajput1
Producción
0-based celebrity index is : 2
Análisis de Complejidad:
- Complejidad de tiempo: O(n)
- Complejidad del espacio: O(1) No se requiere espacio adicional.
- Escribe código para encontrar a la celebridad. No use ninguna estructura de datos como gráficos, pilas, etc., solo tiene acceso a N y HaveAcquaintance (int, int) .
- Implemente el algoritmo usando Queues. ¿Cuál es tu observación? Compare su solución con Encontrar Máximos y Mínimos en una array y Árbol de Torneos . ¿Cuál es el número mínimo de comparaciones que necesitamos (número óptimo de llamadas a HaveAcquaintance() )?
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA