Dados dos enteros A y B , la tarea es verificar si existen dos enteros P y Q en el rango [1, A] y [1, B] respectivamente, de modo que Bitwise XOR de P y Q sea mayor que A y B . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: X = 2, Y = 2
Salida: Sí
Explicación:
Al elegir el valor de P y Q como 1 y 2 respectivamente, da el XOR bit a bit de P y Q como 1^2 = 3, que es mayor que el XOR bit a bit de A y BA ^ B = 0.
Por lo tanto, imprima Sí.Entrada: X = 2, Y = 4
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de ( P, Q) al atravesar todos los números enteros de 1 a X y de 1 a Y y verificar si existe un par tal que su Bitwise XOR sea mayor que Bitwise XOR de X e Y , luego imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there exists any pair (P, Q) whose
// Bitwise XOR is greater than the Bitwise XOR of X and Y
void findWinner(int X, int Y)
{
// Stores the Bitwise XOR of X & Y
int playerA = (X ^ Y);
bool flag = false;
// Traverse all possible pairs
for (int i = 1; i <= X; i++) {
for (int j = 1; j <= Y; j++) {
int val = (i ^ j);
// If a pair exists
if (val > playerA) {
flag = true;
break;
}
}
if (flag)
break;
}
// If a pair is found
if (flag)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
int A = 2, B = 4;
findWinner(A, B);
return 0;
}
C
// C program for the above approach
#include <stdio.h>
#include <stdbool.h>
// Function to check if there exists any pair (P, Q) whose
// Bitwise XOR is greater than the Bitwise XOR of X and Y
void findWinner(int X, int Y)
{
// Stores the Bitwise XOR of X & Y
int playerA = (X ^ Y);
bool flag = false;
// Traverse all possible pairs
for (int i = 1; i <= X; i++) {
for (int j = 1; j <= Y; j++) {
int val = (i ^ j);
// If a pair exists
if (val > playerA) {
flag = true;
break;
}
}
if (flag)
break;
}
// If a pair is found
if (flag)
printf("Yes");
else
printf("No");
}
// Driver Code
int main()
{
int A = 2, B = 4;
findWinner(A, B);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
static void findWinner(int X, int Y)
{
// Stores the Bitwise XOR of X & Y
int playerA = (X ^ Y);
boolean flag = false;
// Traverse all possible pairs
for(int i = 1; i <= X; i++)
{
for(int j = 1; j <= Y; j++)
{
int val = (i ^ j);
// If a pair exists
if (val > playerA)
{
flag = true;
break;
}
}
if (flag)
{
break;
}
}
// If a pair is found
if (flag)
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
// Driver code
public static void main(String[] args)
{
int A = 2, B = 4;
findWinner(A, B);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to check if there exists
# any pair (P, Q) whose Bitwise XOR
# is greater than the Bitwise XOR
# of X and Y
def findWinner(X, Y):
# Stores the Bitwise XOR of X & Y
playerA = (X ^ Y)
flag = False
# Traverse all possible pairs
for i in range(1, X + 1, 1):
for j in range(1, Y + 1, 1):
val = (i ^ j)
# If a pair exists
if (val > playerA):
flag = True
break
if (flag):
break
# If a pair is found
if (flag):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
A = 2
B = 4
findWinner(A, B)
# This code is contributed by bgangwar59
C#
// C# program for the above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
static void findWinner(int X, int Y)
{
// Stores the Bitwise XOR of X & Y
int playerA = (X ^ Y);
bool flag = false;
// Traverse all possible pairs
for(int i = 1; i <= X; i++)
{
for(int j = 1; j <= Y; j++)
{
int val = (i ^ j);
// If a pair exists
if (val > playerA)
{
flag = true;
break;
}
}
if (flag)
{
break;
}
}
// If a pair is found
if (flag)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
// Driver code
public static void Main(String[] args)
{
int A = 2, B = 4;
findWinner(A, B);
}
}
// This code is contributed by amreshkumar3
Javascript
<script>
// JavaScript program for the above approach
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
function findWinner(X,Y)
{
// Stores the Bitwise XOR of X & Y
let playerA = (X ^ Y);
let flag = false;
// Traverse all possible pairs
for(let i = 1; i <= X; i++)
{
for(let j = 1; j <= Y; j++)
{
let val = (i ^ j);
// If a pair exists
if (val > playerA)
{
flag = true;
break;
}
}
if (flag)
{
break;
}
}
// If a pair is found
if (flag)
{
document.write("Yes<br>");
}
else
{
document.write("No<br>");
}
}
// Driver code
let A = 2, B = 4;
findWinner(A, B);
// This code is contributed by unknown2108
</script>
Producción:
No
Complejidad de Tiempo: O(X * Y)
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- Para dos enteros cualesquiera P y Q , el valor máximo de XOR bit a bit es (P + Q) , que solo se puede encontrar cuando no hay bits comunes entre P y Q en su representación binaria .
- Hay dos casos:
- Caso 1: si el jugador A tiene dos números enteros que producen el valor XOR bit a bit máximo, imprima «No» .
- Caso 2: En este caso, debe haber algún bit común entre A y B tal que siempre existan dos enteros P y Q cuyo Bitwise XOR sea siempre mayor que el Bitwise XOR de A y B , donde (P ^ Q) = ( X | Y) .
Por lo tanto, a partir de las observaciones anteriores, la idea es verificar si el valor de A^B dado es igual a A + B o no. Si se encuentra que es cierto, escriba “No” . De lo contrario, escriba «Sí» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
void findWinner(int X, int Y)
{
int first = (X ^ Y);
int second = (X + Y);
// Check for the invalid condition
if (first == second) {
cout << "No";
}
// Otherwise,
else {
cout << "Yes";
}
}
// Driver Code
int main()
{
int A = 2, B = 4;
findWinner(A, B);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
static void findWinner(int X, int Y)
{
int first = (X ^ Y);
int second = (X + Y);
// Check for the invalid condition
if (first == second)
{
System.out.println("No");
}
// Otherwise,
else
{
System.out.println("Yes");
}
}
// Driver code
public static void main(String[] args)
{
int A = 2, B = 4;
findWinner(A, B);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to check if there exists
# any pair (P, Q) whose Bitwise XOR
# is greater than the Bitwise XOR
# of X and Y
def findWinner(X, Y):
first = (X ^ Y)
second = (X + Y)
# Check for the invalid condition
if (first == second):
print ("No")
# Otherwise,
else:
print ("Yes")
# Driver Code
if __name__ == '__main__':
A, B = 2, 4
findWinner(A, B)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
static void findWinner(int X, int Y)
{
int first = (X ^ Y);
int second = (X + Y);
// Check for the invalid condition
if (first == second)
{
Console.Write("No");
}
// Otherwise,
else
{
Console.Write("Yes");
}
}
// Driver code
public static void Main(String[] args)
{
int A = 2, B = 4;
findWinner(A, B);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to check if there exists
// any pair (P, Q) whose Bitwise XOR
// is greater than the Bitwise XOR
// of X and Y
function findWinner(X,Y)
{
let first = (X ^ Y);
let second = (X + Y);
// Check for the invalid condition
if (first == second) {
document.write("No");
}
// Otherwise,
else {
document.write("Yes");
}
}
// Driver Code
let A = 2, B = 4;
findWinner(A, B);
// This code is contributed by patel2127
</script>
Producción:
No
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA