Verifique si existe un par de enteros de dos rangos de modo que su Bitwise XOR exceda ambos rangos

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

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta