Dados dos enteros X e Y , la tarea es encontrar dos números cuyo OR bit a bit sea X y su suma sea Y. Si no existen tales enteros, imprima «-1» .
Ejemplos:
Entrada: X = 7, Y = 11
Salida: 4 7
Explicación:
El OR bit a bit de 4 y 7 es 7 y la suma de dos enteros es 4 + 7 = 11, satisface las condiciones dadas.Entrada: X = 11, Y = 7
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de la array y, si existe algún par que satisfaga la condición dada, imprima esos pares. De lo contrario, imprima «-1» .
Complejidad temporal: O(Y)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de las propiedades de los operadores bit a bit . Considere dos enteros cualesquiera A y B , luego la suma de dos enteros se puede representar como A + B = (A & B) + (A | B) . Ahora, coloque las variables X e Y y cambie la ecuación como:
=> Y = (A & B) + X
=> (A & B) = Y – X
Por lo tanto, las observaciones anteriores se pueden deducir con esta ecuación.
Siga los pasos a continuación para resolver el problema dado:
- Si el valor de Y es menor que X , entonces no habrá solución ya que las operaciones AND bit a bit siempre son no negativas.
- Ahora, para el K -ésimo bit en la representación bit a bit de X e Y , si este bit es ‘1’ en (A&B) y “0” en (A | B) , entonces no habrá soluciones posibles. Esto se debe a que si el AND bit a bit de dos números es 1 , entonces es necesario que el OR bit a bit también sea 1 .
- De lo contrario, siempre es posible elegir dos números enteros A y B que se pueden calcular como A = Y – X y B = X.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define MaxBit 32
using namespace std;
// Function to find the two integers from
// the given sum and Bitwise OR value
int possiblePair(int X, int Y)
{
int Z = Y - X;
// Check if Z is non negative
if (Z < 0) {
cout << "-1";
return 0;
}
// Iterate through all the bits
for (int k = 0; k < MaxBit; k++) {
// Find the kth bit of A & B
int bit1 = (Z >> k) & 1;
// Find the kth bit of A | B
int bit2 = (Z >> k) & 1;
// If bit1 = 1 and bit2 = 0, then
// there will be no possible pairs
if (bit1 && !bit2) {
cout << "-1";
return 0;
}
}
// Print the possible pairs
cout << Z << ' ' << X;
return 0;
}
// Driver Code
int main()
{
int X = 7, Y = 11;
possiblePair(X, Y);
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG{
static int MaxBit = 32;
// Function to find the two integers from
// the given sum and Bitwise OR value
static void possiblePair(int X, int Y)
{
int Z = Y - X;
// Check if Z is non negative
if (Z < 0) {
System.out.print("-1");
}
// Iterate through all the bits
for (int k = 0; k < MaxBit; k++) {
// Find the kth bit of A & B
int bit1 = (Z >> k) & 1;
// Find the kth bit of A | B
int bit2 = (Z >> k) & 1;
// If bit1 = 1 and bit2 = 0, then
// there will be no possible pairs
if (bit1 != 0 && bit2 == 0) {
System.out.print("-1");
}
}
// Print the possible pairs
System.out.print( Z + " " + X);
}
// Driver Code
public static void main(String[] args)
{
int X = 7, Y = 11;
possiblePair(X, Y);
}
}
// This code is contributed by avijitmondal1998.
Python3
# Python 3 program for the above approach
MaxBit = 32
# Function to find the two integers from
# the given sum and Bitwise OR value
def possiblePair(X, Y):
Z = Y - X
# Check if Z is non negative
if (Z < 0):
print("-1")
return 0
# Iterate through all the bits
for k in range(MaxBit):
# Find the kth bit of A & B
bit1 = (Z >> k) & 1
# Find the kth bit of A | B
bit2 = (Z >> k) & 1
# If bit1 = 1 and bit2 = 0, then
# there will be no possible pairs
if (bit1 == 1 and bit2 == 0):
print("-1")
return 0
# Print the possible pairs
print(Z, X)
return 0
# Driver Code
if __name__ == '__main__':
X = 7
Y = 11
possiblePair(X, Y)
# This code is contributed by SURENDRA_GANGWAR.
C#
//C# code for the above approach
using System;
public class GFG{
static int MaxBit = 32;
// Function to find the two integers from
// the given sum and Bitwise OR value
static void possiblePair(int X, int Y)
{
int Z = Y - X;
// Check if Z is non negative
if (Z < 0) {
Console.Write("-1");
}
// Iterate through all the bits
for (int k = 0; k < MaxBit; k++) {
// Find the kth bit of A & B
int bit1 = (Z >> k) & 1;
// Find the kth bit of A | B
int bit2 = (Z >> k) & 1;
// If bit1 = 1 and bit2 = 0, then
// there will be no possible pairs
if (bit1 != 0 && bit2 == 0) {
Console.Write("-1");
}
}
// Print the possible pairs
Console.Write( Z + " " + X);
}
// Driver Code
static public void Main (){
// Code
int X = 7, Y = 11;
possiblePair(X, Y);
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// Javascript program for the above approach
let MaxBit = 32;
// Function to find the two integers from
// the given sum and Bitwise OR value
function possiblePair(X, Y) {
let Z = Y - X;
// Check if Z is non negative
if (Z < 0) {
document.write("-1");
return 0;
}
// Iterate through all the bits
for (let k = 0; k < MaxBit; k++) {
// Find the kth bit of A & B
let bit1 = (Z >> k) & 1;
// Find the kth bit of A | B
let bit2 = (Z >> k) & 1;
// If bit1 = 1 and bit2 = 0, then
// there will be no possible pairs
if (bit1 && !bit2) {
document.write("-1");
return 0;
}
}
// Print the possible pairs
document.write(Z + " " + X);
return 0;
}
// Driver Code
let X = 7,
Y = 11;
possiblePair(X, Y);
// This code is contributed by gfgking.
</script>
4 7
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA