Dados dos enteros X e Y , la tarea es encontrar los dos enteros que tienen suma X y Bitwise XOR igual a Y .
Ejemplos:
Entrada: X = 17, Y = 13
Salida: 2 15
Explicación: 2 + 15 = 17 y 2 ^ 15 = 13Entrada: X = 1870807699, Y = 259801747
Salida: 805502976 1065304723
Enfoque ingenuo: consulte la publicación anterior de este artículo para conocer el enfoque más simple para resolver el problema.
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
A + B = (A ^ B) + 2 * (A y B)
=> X = Y + 2 * (A y B)Al calcular la suma, si ambos bits son 1 (es decir, AND es 1), el bit resultante es 0 y 1 se agrega como acarreo, lo que significa que cada bit en AND se desplaza a la izquierda por 1, es decir, el valor de AND se multiplica por 2 y añadido.
Reordenando los términos se obtiene la expresión (A&B) = (X – Y) / 2.
Esto verifica la observación anterior.
Existen los siguientes casos:
- Si X < Y: En este caso, la solución no existe porque (A & B) se vuelve negativa, lo cual no es posible.
- Si X – Y es impar: En este caso, la solución no existe porque (X – Y) no es divisible por 2.
- Si X = Y: En este caso, A & B = 0. Por lo tanto, el valor mínimo de A debe ser 0 y el valor de B debe ser Y para satisfacer las ecuaciones dadas.
- De lo contrario: A&B = (X – Y)/2 se cumple, solo cuando ((X – Y)/2) & Y es igual a 0. Si es cierto, A = (X – Y)/2 y B = A + Y. De lo contrario, A = -1 y B = -1.
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 find the value of A and
// B whose sum is X and xor is Y
void findNums(int X, int Y)
{
// Initialize the two numbers
int A, B;
// Case 1: X < Y
if (X < Y) {
A = -1;
B = -1;
}
// Case 2: X-Y is odd
else if (abs(X - Y) & 1) {
A = -1;
B = -1;
}
// Case 3: If both Sum and XOR
// are equal
else if (X == Y) {
A = 0;
B = Y;
}
// Case 4: If above cases fails
else {
// Update the value of A
A = (X - Y) / 2;
// Check if A & Y value is 0
if ((A & Y) == 0) {
// If true, update B
B = (A + Y);
}
// Otherwise assign -1 to A,
// -1 to B
else {
A = -1;
B = -1;
}
}
// Print the numbers A and B
cout << A << " " << B;
}
// Driver Code
int main()
{
// Given Sum and XOR of 2 numbers
int X = 17, Y = 13;
// Function Call
findNums(X, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the value of A and
// B whose sum is X and xor is Y
static void findNums(int X, int Y)
{
// Initialize the two numbers
int A, B;
// Case 1: X < Y
if (X < Y)
{
A = -1;
B = -1;
}
// Case 2: X-Y is odd
else if (((Math.abs(X - Y)) & 1) != 0)
{
A = -1;
B = -1;
}
// Case 3: If both Sum and XOR
// are equal
else if (X == Y)
{
A = 0;
B = Y;
}
// Case 4: If above cases fails
else
{
// Update the value of A
A = (X - Y) / 2;
// Check if A & Y value is 0
if ((A & Y) == 0)
{
// If true, update B
B = (A + Y);
}
// Otherwise assign -1 to A,
// -1 to B
else
{
A = -1;
B = -1;
}
}
// Print the numbers A and B
System.out.print(A + " " + B);
}
// Driver Code
public static void main(String[] args)
{
// Given Sum and XOR of 2 numbers
int X = 17, Y = 13;
// Function Call
findNums(X, Y);
}
}
// This code is contributed by susmitakundugoaldanga
Python
# Python program for the above approach # Function to find the value of A and # B whose sum is X and xor is Y def findNums(X, Y): # Initialize the two numbers A = 0; B = 0; # Case 1: X < Y if (X < Y): A = -1; B = -1; # Case 2: X-Y is odd elif (((abs(X - Y)) & 1) != 0): A = -1; B = -1; # Case 3: If both Sum and XOR # are equal elif (X == Y): A = 0; B = Y; # Case 4: If above cases fails else: # Update the value of A A = (X - Y) // 2; # Check if A & Y value is 0 if ((A & Y) == 0): # If True, update B B = (A + Y); # Otherwise assign -1 to A, # -1 to B else: A = -1; B = -1; # Print the numbers A and B print A; print B; # Driver Code if __name__ == '__main__': # Given Sum and XOR of 2 numbers X = 17; Y = 13; # Function Call findNums(X, Y); # This code is contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the value of A and
// B whose sum is X and xor is Y
static void findNums(int X, int Y)
{
// Initialize the two numbers
int A, B;
// Case 1: X < Y
if (X < Y)
{
A = -1;
B = -1;
}
// Case 2: X-Y is odd
else if (((Math.Abs(X - Y)) & 1) != 0)
{
A = -1;
B = -1;
}
// Case 3: If both Sum and XOR
// are equal
else if (X == Y)
{
A = 0;
B = Y;
}
// Case 4: If above cases fails
else
{
// Update the value of A
A = (X - Y) / 2;
// Check if A & Y value is 0
if ((A & Y) == 0)
{
// If true, update B
B = (A + Y);
}
// Otherwise assign -1 to A,
// -1 to B
else
{
A = -1;
B = -1;
}
}
// Print the numbers A and B
Console.Write(A + " " + B);
}
// Driver Code
public static void Main(String[] args)
{
// Given Sum and XOR of 2 numbers
int X = 17, Y = 13;
// Function Call
findNums(X, Y);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to implement the above approach
// Function to find the value of A and
// B whose sum is X and xor is Y
function findNums(X, Y)
{
// Initialize the two numbers
let A, B;
// Case 1: X < Y
if (X < Y) {
A = -1;
B = -1;
}
// Case 2: X-Y is odd
else if (Math.abs(X - Y) & 1) {
A = -1;
B = -1;
}
// Case 3: If both Sum and XOR
// are equal
else if (X == Y) {
A = 0;
B = Y;
}
// Case 4: If above cases fails
else {
// Update the value of A
A = (X - Y) / 2;
// Check if A & Y value is 0
if ((A & Y) == 0) {
// If true, update B
B = (A + Y);
}
// Otherwise assign -1 to A,
// -1 to B
else {
A = -1;
B = -1;
}
}
// Print the numbers A and B
document.write(A + " " + B);
}
// Driver Code
// Given Sum and XOR of 2 numbers
let X = 17, Y = 13;
// Function Call
findNums(X, Y);
</script>
2 15
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