Cuente las formas de generar pares que tengan Bitwise XOR y Bitwise AND iguales a X e Y respectivamente

Dados dos enteros X e Y , la tarea es encontrar el número total de formas de generar un par de enteros A y B tales que Bitwise XOR y Bitwise AND entre A y B sean X e Y respectivamente.

Ejemplos:

Entrada: X = 2, Y = 5
Salida: 2
Explicación:
Los dos pares posibles son (5, 7) y (7, 5).
Par 1: (5, 7)
AND bit a bit = 5 & 7 = 2
XOR bit a bit = 5 ^ 7 = 5
Par 2: (7, 5)
AND bit a bit = 7 & 5 = 2
XOR bit a bit = 7 ^ 5 = 5

Entrada: X = 7, Y = 5
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es elegir el máximo entre X e Y y configurar todos sus bits y luego verificar todos los pares posibles desde 0 hasta ese número máximo, digamos M . Si para cualquier par de A y B , A & B y A⊕B se vuelve igual a X e Y respectivamente, entonces incremente la cuenta . Imprime el valor final de count después de verificar todos los pares posibles.
Complejidad Temporal: O(M ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es generar todas las combinaciones posibles de bits en cada posición. Hay 4 posibilidades para el i ^-ésimo bit en X e Y que son las siguientes:

Si X _i = 0 y Y _i = 1, entonces A _i = 1 y B _i = 1.
Si X _i = 1 e Y _i = 1, entonces no existe ninguna asignación de bits posible.
Si X _i = 0 y Y _i = 0 entonces A _i = 0 y B _i = 0.
Si X _i = 1 y Y _i = 0, entonces A _i = 0 y B _i = 1 o A _i = 1 y B _i = 0, donde A _i , B _i , X _i y Y _i representan i- ^ésimo bit en cada de ellos.

Siga los pasos a continuación para resolver el problema:

Inicialice el contador como 1 .
Para el i ^ésimo bit , si X _i e Y _i son iguales a 1 , imprima 0 .
Si en el i- ^ésimo bit , X _i es 1 e Y _i es 0 , entonces multiplique el contador por 2 ya que hay 2 opciones.
Después de eso, divide X e Y cada vez por 2 .
Repita los pasos anteriores para cada i- ^ésimo bit hasta que ambos se conviertan en 0 e imprima el valor del contador .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
int countOfPairs(int x, int y)
{
    // Stores the count of pairs
    int counter = 1;
 
    // Iterate till any bit are set
    while (x || y) {
 
        // Extract i-th bit
        // of X and Y
        int bit1 = x % 2;
        int bit2 = y % 2;
 
        // Divide X and Y by 2
        x >>= 1;
        y >>= 1;
 
        // If Xi = 1 and Yi = 2,
        // multiply counter by 2
        if (bit1 == 1 and bit2 == 0) {
 
            // Increase required count
            counter *= 2;
            continue;
        }
 
        // If Xi =1 and Yi = 1
        if (bit1 & bit2) {
 
            // No answer exists
            counter = 0;
            break;
        }
    }
 
    // Return the final count
    return counter;
}
 
// Driver Code
int main()
{
    // Given X and Y
    int X = 2, Y = 5;
 
    // Function Call
    cout << countOfPairs(X, Y);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
static int countOfPairs(int x, int y)
{
  // Stores the count of pairs
  int counter = 1;
 
  // Iterate till any bit are set
  while (x > 0 || y > 0)
  {
    // Extract i-th bit
    // of X and Y
    int bit1 = x % 2;
    int bit2 = y % 2;
 
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
 
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0)
    {
      // Increase required count
      counter *= 2;
      continue;
    }
 
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0)
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
 
  // Return the final count
  return counter;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given X and Y
  int X = 2, Y = 5;
 
  // Function Call
  System.out.print(countOfPairs(X, Y));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach
 
# Function to return the count of
# possible pairs of A and B whose
# Bitwise XOR is X and Y respectively
def countOfPairs(x, y):
 
    # Stores the count of pairs
    counter = 1
 
    # Iterate till any bit are set
    while(x or y):
 
        # Extract i-th bit
        # of X and Y
        bit1 = x % 2
        bit2 = y % 2
 
        # Divide X and Y by 2
        x >>= 1
        y >>= 1
 
        # If Xi = 1 and Yi = 2,
        # multiply counter by 2
        if (bit1 == 1 and bit2 == 0):
             
            # Increase required count
            counter *= 2
            continue
 
        # If Xi =1 and Yi = 1
        if(bit1 & bit2):
 
            # No answer exists
            counter = 0
            break
 
    # Return the final count
    return counter
 
# Driver Code
 
# Given X and Y
X = 2
Y = 5
 
# Function call
print(countOfPairs(X, Y))
 
# This code is contributed by Shivam Singh

C#

// C# program for
// the above approach
using System;
class GFG{
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
static int countOfPairs(int x, int y)
{
  // Stores the count of pairs
  int counter = 1;
 
  // Iterate till any bit are set
  while (x > 0 || y > 0)
  {
    // Extract i-th bit
    // of X and Y
    int bit1 = x % 2;
    int bit2 = y % 2;
 
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
 
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0)
    {
      // Increase required count
      counter *= 2;
      continue;
    }
 
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0)
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
 
  // Return the readonly count
  return counter;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given X and Y
  int X = 2, Y = 5;
 
  // Function Call
  Console.Write(countOfPairs(X, Y));
}
}
  
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for
// the above approach
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
function countOfPairs(x, y)
{
  // Stores the count of pairs
  let counter = 1;
  
  // Iterate till any bit are set
  while (x > 0 || y > 0)
  {
    // Extract i-th bit
    // of X and Y
    let bit1 = x % 2;
    let bit2 = y % 2;
  
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
  
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0)
    {
      // Increase required count
      counter *= 2;
      continue;
    }
  
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0)
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
  
  // Return the final count
  return counter;
}
 
// Driver code
 
   // Given X and Y
  let X = 2, Y = 5;
  
  // Function Call
  document.write(countOfPairs(X, Y));
                             
</script>

Producción:

Complejidad de tiempo: O(log M), ya que estamos usando un bucle para atravesar y cada vez estamos decrementando por división de piso de 2.
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta