Dados N pares de enteros, cada entero está entre 1 y M , la tarea es verificar si existen dos enteros x e y tales que al menos uno de los enteros esté presente en cada uno de los pares.
Ejemplos:
Entrada: N = 7, M = 6, arr[] = {{5, 6}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5} , {4, 5}}
Salida: NO
Explicación: No se puede elegir ninguna x o y porque
para cada uno de esos pares puede encontrar un par dado
donde ambos números son diferentes de los enteros elegidos.Entrada: N = 5, M = 6, {{6, 4}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}
Salida: SÍ
Explicación: Elija x = 5 y y = 3.
Porque ya sea x o y está presente en todos los pares.
Enfoque 1: El problema se puede resolver con base en la siguiente idea:
Considere que el primer par de la array es el par deseado (x, y). Si hay un par en el que ninguno de los elementos está presente, entonces uno de ese par dado debe ser parte del par deseado.
Así que ahora hay un total de 4 elementos que pueden formar el par deseado. Comprueba todas las combinaciones posibles de parejas y encuentra si alguna de ellas es la pareja deseada.
Siga los pasos para resolver el problema:
- Cree 2 variables (x1, y1) que contengan cada uno de los primeros elementos de la array.
- Ahora atraviesa de i = 0 a N-1 :
- Compruebe si ninguno de x1 o y1 está presente en el par.
- Si la condición anterior es verdadera, considere que los elementos son otro par (x2, y2) .
- Ahora verifique las 6 combinaciones posibles de x1, x2, y1 e y2.
- Si existe una de estas combinaciones en cada par dado, entonces la solución es posible.
- De lo contrario, no existe tal par.
A continuación se muestra la implementación del enfoque anterior.
Java
// Java code ot implement the approach
class GFG
{
// Function to check if x or y is present
// in each of the given pairs
static boolean check(int x, int y, int[][] arr) {
for (int i = 0; i < arr.length; i++)
if (x != arr[i][0] && y != arr[i][0] && x != arr[i][1] && y != arr[i][1])
return false;
return true;
}
// Function to find the desired pair
static String pairs(int n, int[][] arr) {
int x1 = arr[0][0];
int y1 = arr[0][1];
int x2 = 0;
int y2 = 0;
// Finding values which do not contain
// the values in 1st array index
for (int i = 1; i < n; i++) {
if (x1 != arr[i][0] && x1 != arr[i][1] && y1 != arr[i][0] && y1 != arr[i][1]) {
x2 = arr[i][0];
y2 = arr[i][1];
}
}
if (check(x1, x2, arr) || check(x1, y1, arr) || check(x1, y2, arr) || check(x2, y1, arr) || check(x2, y2, arr)
|| check(y1, y2, arr))
return "Yes";
else
return "No";
}
// Driver code
public static void main(String[] args) {
int N = 6;
int M = 5;
int[][] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } };
// Function call
System.out.println(pairs(N, arr));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 code ot implement the approach # Function to check if x or y is present # in each of the given pairs def check(x, y, arr): for i in range(len(arr)): if x != arr[i][0] and y != arr[i][0] \ and x != arr[i][1] and y != arr[i][1]: return False return True # Function to find the desired pair def pairs(n, arr): x1 = arr[0][0] y1 = arr[0][1] x2 = 0 y2 = 0 # Finding values which do not contain # the values in 1st array index for i in range(1, n): if x1 != arr[i][0] and x1 != arr[i][1] \ and y1 != arr[i][0] and y1 != arr[i][1]: x2 = arr[i][0] y2 = arr[i][1] if check(x1, x2, arr) or check(x1, y1, arr) or \ check(x1, y2, arr) or check(x2, y1, arr) or \ check(x2, y2, arr) or check(y1, y2, arr): return 'YES' else: return 'NO' # Driver code if __name__ == '__main__': N = 6 M = 5 arr = [[2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]] # Function call print(pairs(N, arr))
C#
// C# code ot implement the approach
using System;
class GFG {
// Function to check if x or y is present
// in each of the given pairs
static bool check(int x, int y, int[, ] arr)
{
for (int i = 0; i < arr.Length; i++)
if (x != arr[i, 0] && y != arr[i, 0]
&& x != arr[i, 1] && y != arr[i, 1])
return false;
return true;
}
// Function to find the desired pair
static string pairs(int n, int[, ] arr)
{
int x1 = arr[0, 0];
int y1 = arr[0, 1];
int x2 = 0;
int y2 = 0;
// Finding values which do not contain
// the values in 1st array index
for (int i = 1; i < n; i++) {
if (x1 != arr[i, 0] && x1 != arr[i, 1]
&& y1 != arr[i, 0] && y1 != arr[i, 1]) {
x2 = arr[i, 0];
y2 = arr[i, 1];
}
}
if (check(x1, x2, arr) || check(x1, y1, arr)
|| check(x1, y2, arr) || check(x2, y1, arr)
|| check(x2, y2, arr) || check(y1, y2, arr))
return "Yes";
else
return "No";
}
// Driver code
public static void Main(string[] args)
{
int N = 6;
int M = 5;
int[, ] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 },
{ 3, 4 }, { 3, 5 }, { 4, 5 } };
// Function call
Console.WriteLine(pairs(N, arr));
}
}
// This code is contributed by phasing17
NO
Complejidad temporal: O(N).
Espacio Auxiliar: O(1)
Enfoque 2: La idea de este enfoque también es similar a la mencionada anteriormente. La única diferencia es que:
En el caso anterior, estábamos utilizando todas las combinaciones posibles. Si se observa cuidadosamente, podemos concluir que debe haber un valor del par (x1, y1) y un valor de (x2, y2) porque si esto no se hace, uno de los pares será despreciado.
Entonces, en este caso, solo buscaremos 4 pares posibles, es decir, (x1, y2), (x1, x2), (y1, y2) y (x2, y1).
Siga los pasos mencionados a continuación para implementar la idea:
- Considere el primer elemento del primer par. Digamos que (x1, y1) es un par, luego considere x1 .
- Encuentra el par donde x1 no existe.
- Considere ese par como (x2, y2) y tome el valor x2 :
- Compruebe todos los demás pares si (x1, x2) existe en cada par.
- Si sale, imprima ‘Sí’, de lo contrario, repita el paso 3 con el valor y2.
- Si el par (x1, y2) sale en cada par, imprima ‘Sí’; de lo contrario, repita los pasos 1 a 3 con el valor y1 .
- Si después de la operación anterior todavía no hay ningún par, entonces ese par no es posible.
A continuación se muestra la implementación del enfoque anterior.
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Function to check if x or y is present in each of the
// given pairs
public static boolean check(int x, int y, int[][] arr,
int n)
{
// Loop to check if x or y is present in the pairs
for (int i = 1; i < n; i++) {
if (arr[i][0] == y || arr[i][1] == y
|| arr[i][0] == x || arr[i][1] == x) {
continue;
}
else {
// If x and y are not present in all the
// array pairs
return true;
}
}
return false;
}
// Function to find the index of the first pair where x
// is not present
public static int findIndex(int x, int[][] arr, int n)
{
for (int i = 1; i < n; i++) {
if (arr[i][0] != x && arr[i][1] != x) {
return i;
}
}
return n;
}
// Function to find if the required pair is present in
// array or not.
public static String find(int[][] a, int n)
{
int x = a[0][0];
int k = findIndex(x, a, n);
// Taking the first value of kth index
if (k >= n) {
return "YES";
}
int y = a[k][0];
int flag = 0;
// If x and y are not in all array pairs
if (check(x, y, a, n)) {
// Considering second value of kth index
y = a[k][1];
// If x and y are not in all array pairs
if (check(x, y, a, n)) {
// Second element is in 1st index
x = a[0][1];
k = findIndex(x, a, n);
if (k >= n) {
return "YES";
}
// Taking the first value of kth index
y = a[k][0];
if (check(x, y, a, n)) {
// Considering second value of kth index
y = a[k][1];
if (check(x, y, a, n)) {
return "NO";
}
}
}
}
return "YES";
}
public static void main(String[] args)
{
int N = 6;
int M = 5;
int[][] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 },
{ 3, 4 }, { 3, 5 }, { 4, 5 } };
// Function call
System.out.print(find(arr, N));
}
}
// This code is contributed by lokesh (lokeshmvs21).
Python3
# Python 3 code to implement the approach # Function to check if x or y is present # in each of the given pairs def check(x, y, arr, n): # Loop to check if x or y is present in the pairs for i in range(1, n): if arr[i][0] == y or arr[i][1] == y \ or arr[i][0] == x or arr[i][1] == x: continue else: # If x and y are not present # in all the array pairs return True return False # Function to find the index of the # first pair where x is not present def findIndex(x, arr, n): for i in range(1, n): if arr[i][0] != x and arr[i][1] != x: return i return n # Function to find if the # required pair is present in array or not def find(a, n): x = a[0][0] k = findIndex(x, a, n) # Taking the fisrt value of kth index if k >= n: return 'YES' y = a[k][0] flag = 0 # If x and y are not in all array pairs if check(x, y, a, n): # Considering second value of kth index y = a[k][1] # If x and y are not in all array pairs if check(x, y, a, n): # Cecond element in 1st index x = a[0][1] k = findIndex(x, a, n) if k >= n: return 'YES' # Taking the fisrt value of kth index y = a[k][0] if check(x, y, a, n): # Considering second value of kth index y = a[k][1] if check(x, y, a, n): return 'NO' return 'YES' # Driver code if __name__ == '__main__': N = 6 M = 5 arr = [[2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]] # Function call print(find(arr, N))
NO
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anveshsaxena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA