Dada una array binaria de tamaño N * N , mat[][] . El valor en la celda (i, j) indica lo que la i-ésima persona dice sobre la j-ésima persona. Una persona x se considera honesta si siempre dice la verdad. Si la persona x dice mentiras a veces y verdad a veces, entonces es un mentiroso.
- Si mat[i][j] = 0, entonces la i-ésima persona dice que la j-ésima persona es una mentirosa.
- Si mat[i][j] = 1, entonces la i-ésima persona dice que la j-ésima persona es honesta.
- Si mat[i][j] = 2, entonces la i-ésima persona no comenta sobre la j-ésima persona.
La tarea es encontrar el máximo de personas honestas.
Ejemplos:
Entrada: mat = {{2, 1, 2},
{1, 2, 2},
{2, 0, 2}}
Salida: 2
Explicación: Cada persona hace una sola declaración.
La persona 0 afirma que la persona 1 es honesta.
La persona 1 afirma que la persona 0 es honesta.
La persona 2 dice que la persona 1 es mentirosa.
Tomemos a la persona 2 como clave.
- Suponiendo que la persona 2 es honesta:
- Basado en la declaración hecha por la persona 2, la persona 1 es una mentirosa.
- Ahora la persona 1 es mentirosa y la persona 2 es honesta.
- Basado en la declaración hecha por la persona 1, y dado que la persona 1 es mentirosa, podría ser:
- verdadero. Habrá una contradicción en este caso y esta suposición no es válida.
- mentir. En este caso, la persona 0 también es mentirosa y mintió.
- Seguir a esa persona 2 es honesto, solo puede haber una persona honesta.
- Suponiendo que la persona 2 es mentirosa:
- Basado en la declaración hecha por la persona 2, y dado que la persona 2 es mentirosa, podría ser:
- verdadero. Siguiendo este escenario, la persona 0 y 1 son mentirosas como se explicó anteriormente.
- Seguir a esa persona 2 es mentiroso pero dicho la verdad, no habrá persona honesta.
- mintiendo. En este caso la persona 1 es honesta.
- Como la persona 1 es honesta, la persona 0 también lo es.
- Después de que la persona 2 es mentirosa y mintió, habrá dos personas honestas.
- A lo sumo 2 personas son honestas en el mejor de los casos.
- Entonces la respuesta es 2.
Entrada: mat = {{2, 0},
{0, 2}}
Salida: 1
Enfoque: Puede haber 2 N combinaciones de opiniones entre N personas. La idea es considerar 2 N números y asumir su representación binaria como el orden posible de la realidad de las personas. 0 bit representa que la persona es mentirosa y 1 representa que la persona es honesta . Recorra todos los números, si un bit en el número es 1 , suponga que la persona indexada es honesta y luego confirme esta suposición. Para confirmar la suposición, verifique todos los bits jth del número con respecto a este índice y lo que dice sobre jthpersona en la array. Siga los pasos que se mencionan a continuación:
- Obtenga el tamaño de la array, es decir , N.
- Calcule el número de combinaciones totales posibles.
- Iterar a través de todos los números de 0 a 2 N .
- Detecta los setbits (honestos) en el formato binario de este número (combinación) e incrementa el contador.
- Compruebe si el bit «1» dado implica un honesto o un mentiroso.
- Una persona i no es válida si miente.
- Si j-ésimo bit es 0 en combinación número y persona i dice que j es honesto.
- si jth bit es 1 en número de combinación y persona i dice que j es una guarida.
- Si la persona i es válida, actualice la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility Function
bool Is_Good(int n, int index)
{
return (n >> index) & 1;
}
// Function to count maximum honest persons
int MaximumHonest(vector<vector<int> >& mat)
{
int N = mat.size();
int ans = 0;
// Getting all the possible combinations
int comb = pow(2, N);
// Loop to find maximum honest persons
for (int i = 0; i < comb; i++) {
bool isValid = true;
int counter = 0;
for (int person = 0; person < N;
person++) {
// If the person is a liar
if (!Is_Good(i, person))
continue;
counter++;
// Checking validity of "persons"
// being honest and if "person"
// is honest then total number
// of honest persons
for (int j = 0; j < N; j++) {
if ((!Is_Good(i, j)
&& mat[person][j] == 1)
|| (Is_Good(i, j)
&& mat[person][j]
== 0)) {
isValid = false;
break;
}
}
}
if (isValid)
ans = max(ans, counter);
}
return ans;
}
// Driver code
int main()
{
vector<vector<int> > mat{ { 2, 0 },
{ 0, 2 } };
int res = MaximumHonest(mat);
cout << res;
return 0;
}
Java
// Java program to implement the above approach
import java.util.*;
class GFG{
// Utility Function
static boolean Is_Good(int n, int index)
{
return ((n >> index) & 1) >0?true:false;
}
// Function to count maximum honest persons
static int MaximumHonest(int [][] mat)
{
int N = mat[0].length;
int ans = 0;
// Getting all the possible combinations
int comb = (int) Math.pow(2, N);
// Loop to find maximum honest persons
for (int i = 0; i < comb; i++) {
boolean isValid = true;
int counter = 0;
for (int person = 0; person < N;
person++) {
// If the person is a liar
if (!Is_Good(i, person))
continue;
counter++;
// Checking validity of "persons"
// being honest and if "person"
// is honest then total number
// of honest persons
for (int j = 0; j < N; j++) {
if ((!Is_Good(i, j)
&& mat[person][j] == 1)
|| (Is_Good(i, j)
&& mat[person][j]
== 0)) {
isValid = false;
break;
}
}
}
if (isValid)
ans = Math.max(ans, counter);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int [][]mat = { { 2, 0 },
{ 0, 2 } };
int res = MaximumHonest(mat);
System.out.print(res);
}
}
// This code is contributed by 29AjayKumar
Python3
# python3 program to implement the above approach # Utility Function def Is_Good(n, index): return (n >> index) & 1 # Function to count maximum honest persons def MaximumHonest(mat): N = len(mat) ans = 0 # Getting all the possible combinations comb = pow(2, N) # Loop to find maximum honest persons for i in range(0, comb): isValid = True counter = 0 for person in range(0, N): # If the person is a liar if (not Is_Good(i, person)): continue counter += 1 # Checking validity of "persons" # being honest and if "person" # is honest then total number # of honest persons for j in range(0, N): if ((not Is_Good(i, j) and mat[person][j] == 1) or (Is_Good(i, j) and mat[person][j] == 0)): isValid = False break if (isValid): ans = max(ans, counter) return ans # Driver code if __name__ == "__main__": mat = [[2, 0], [0, 2]] res = MaximumHonest(mat) print(res) # This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript code for the above approach
// Utility Function
function Is_Good(n, index) {
return (n >> index) & 1;
}
// Function to count maximum honest persons
function MaximumHonest(mat) {
let N = mat.length;
let ans = 0;
// Getting all the possible combinations
let comb = Math.pow(2, N);
// Loop to find maximum honest persons
for (let i = 0; i < comb; i++) {
let isValid = true;
let counter = 0;
for (let person = 0; person < N;
person++) {
// If the person is a liar
if (!Is_Good(i, person))
continue;
counter++;
// Checking validity of "persons"
// being honest and if "person"
// is honest then total number
// of honest persons
for (let j = 0; j < N; j++) {
if ((!Is_Good(i, j)
&& mat[person][j] == 1)
|| (Is_Good(i, j)
&& mat[person][j]
== 0)) {
isValid = false;
break;
}
}
}
if (isValid)
ans = Math.max(ans, counter);
}
return ans;
}
// Driver code
let mat = [[2, 0],
[0, 2]];
let res = MaximumHonest(mat);
document.write(res);
// This code is contributed by Potta Lokesh
</script>
C#
// C# program to implement the above approach
using System;
class GFG {
// Utility Function
static bool Is_Good(int n, int index)
{
return ((n >> index) & 1) == 1;
}
// Function to count maximum honest persons
static int MaximumHonest(int[, ] mat)
{
int N = mat.GetLength(0);
int ans = 0;
// Getting all the possible combinations
int comb = (int)Math.Pow(2, N);
// Loop to find maximum honest persons
for (int i = 0; i < comb; i++) {
bool isValid = true;
int counter = 0;
for (int person = 0; person < N; person++) {
// If the person is a liar
if (!Is_Good(i, person))
continue;
counter++;
// Checking validity of "persons"
// being honest and if "person"
// is honest then total number
// of honest persons
for (int j = 0; j < N; j++) {
if ((!Is_Good(i, j)
&& mat[person, j] == 1)
|| (Is_Good(i, j)
&& mat[person, j] == 0)) {
isValid = false;
break;
}
}
}
if (isValid)
ans = Math.Max(ans, counter);
}
return ans;
}
// Driver code
public static void Main()
{
int[, ] mat = { { 2, 0 }, { 0, 2 } };
int res = MaximumHonest(mat);
Console.Write(res);
}
}
// This code is contributed by Samim Hossain Mondal.
Producción
1
Complejidad temporal: O(2 N * N * N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA