Encuentra dos números a partir de su suma y XOR – Part 1

Posted on by Rudeus Greyrat

Dada la suma y xor de dos números X e Y st sum y xor  \en [0, 2^{64}-1] , necesitamos encontrar los números que minimizan el valor de X . Ejemplos:

Input : S = 17
        X = 13
Output : a = 2
         b = 15

Input : S = 1870807699 
        X = 259801747
Output : a = 805502976
         b = 1065304723

Input : S = 1639
        X = 1176
Output : No such numbers exist

Variables utilizadas: X ==> XOR de dos números S ==> Suma de dos números X[i] ==> Valor del i-ésimo bit en XS[i] ==> Valor del i-ésimo bit en S

Una solución simple es generar todos los pares posibles con XOR dado. Para generar todos los pares, podemos seguir las siguientes reglas.

  1. Si X[i] es 1, entonces tanto a[i] como b[i] deberían ser diferentes, tenemos dos casos.
  2. Si X[i] es 0, entonces tanto a[i] como b[i] deberían ser iguales. tenemos dos casos.
    1. Si X[i] = 0 y A[i] = 0, entonces a[i] = b[i] = 0. Solo una posibilidad para este bit.
    2. Si X[i] = 0 y A[i] = 1, entonces a[i] = b[i] = 1. Solo una posibilidad para este bit.
    3. Si X[i] = 1 y A[i] = 0, entonces (a[i] = 1 y b[i] = 0) o (a[i] = 0 y b[i] = 1), podemos elige cualquiera de los dos.
    4. Si X[i] = 1 y A[i] = 1, el resultado no es posible (Nota X[i] = 1 significa bits diferentes)

Deje que la suma sea S y XOR sea X.

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

C++

// CPP program to find two numbers with
// given Sum and XOR such that value of
// first number is minimum.
#include <iostream>
using namespace std;
 
// Function that takes in the sum and XOR
// of two numbers and generates the two
// numbers such that the value of X is
// minimized
void compute(unsigned long int S,
            unsigned long int X)
{
    unsigned long int A = (S - X)/2;
 
    int a = 0, b = 0;
 
    // Traverse through all bits
    for (int i=0; i<8*sizeof(S); i++)
    {
        unsigned long int Xi = (X & (1 << i));
        unsigned long int Ai = (A & (1 << i));
        if (Xi == 0 && Ai == 0)
        {
            // Let us leave bits as 0.
        }
        else if (Xi == 0 && Ai > 0)
        {
            a = ((1 << i) | a);
            b = ((1 << i) | b);
        }
        else if (Xi > 0 && Ai == 0)
        {
            a = ((1 << i) | a);
 
            // We leave i-th bit of b as 0.
        }
        else // (Xi == 1 && Ai == 1)
        {
            cout << "Not Possible";
            return;
        }
    }
 
    cout << "a = " << a << endl << "b = " << b;
}
 
// Driver function
int main()
{
    unsigned long int S = 17, X = 13;
    compute(S, X);
    return 0;
}

Java

// Java program to find two numbers with
// given Sum and XOR such that value of
// first number is minimum.
class GFG {
 
// Function that takes in the sum and XOR
// of two numbers and generates the two
// numbers such that the value of X is
// minimized
static void compute(long S, long X)
{
    long A = (S - X)/2;
    int a = 0, b = 0;
        final int LONG_FIELD_SIZE     = 8;
 
    // Traverse through all bits
    for (int i=0; i<8*LONG_FIELD_SIZE; i++)
    {
        long Xi = (X & (1 << i));
        long Ai = (A & (1 << i));
        if (Xi == 0 && Ai == 0)
        {
            // Let us leave bits as 0.
        }
        else if (Xi == 0 && Ai > 0)
        {
            a = ((1 << i) | a);
            b = ((1 << i) | b);
        }
        else if (Xi > 0 && Ai == 0)
        {
            a = ((1 << i) | a);
 
            // We leave i-th bit of b as 0.
        }
        else // (Xi == 1 && Ai == 1)
        {
            System.out.println("Not Possible");
            return;
        }
    }
 
    System.out.println("a = " + a +"\nb = " + b);
}
 
// Driver function
    public static void main(String[] args) {
        long S = 17, X = 13;
    compute(S, X);
 
    }
}
// This code is contributed by RAJPUT-JI

Python3

# Python program to find two numbers with
# given Sum and XOR such that value of
# first number is minimum.
 
 
# Function that takes in the sum and XOR
# of two numbers and generates the two
# numbers such that the value of X is
# minimized
def compute(S, X):
    A = (S - X)//2
    a = 0
    b = 0
 
    # Traverse through all bits
    for i in range(64):
        Xi = (X & (1 << i))
        Ai = (A & (1 << i))
        if (Xi == 0 and Ai == 0):
            # Let us leave bits as 0.
            pass
             
        elif (Xi == 0 and Ai > 0):
            a = ((1 << i) | a)
            b = ((1 << i) | b)
         
        elif (Xi > 0 and Ai == 0):
            a = ((1 << i) | a)
            # We leave i-th bit of b as 0.
 
        else: # (Xi == 1 and Ai == 1)
            print("Not Possible")
            return
 
    print("a = ",a)
    print("b =", b)
 
 
# Driver function
S = 17
X = 13
compute(S, X)
 
# This code is contributed by ankush_953

C#

// C# program to find two numbers with
// given Sum and XOR such that value of
// first number is minimum.
using System;
 
public class GFG {
 
// Function that takes in the sum and XOR
// of two numbers and generates the two
// numbers such that the value of X is
// minimized
static void compute(long S, long X)
{
    long A = (S - X)/2;
    int a = 0, b = 0;
 
 
    // Traverse through all bits
    for (int i=0; i<8*sizeof(long); i++)
    {
        long Xi = (X & (1 << i));
        long Ai = (A & (1 << i));
        if (Xi == 0 && Ai == 0)
        {
            // Let us leave bits as 0.
        }
        else if (Xi == 0 && Ai > 0)
        {
            a = ((1 << i) | a);
            b = ((1 << i) | b);
        }
        else if (Xi > 0 && Ai == 0)
        {
            a = ((1 << i) | a);
 
            // We leave i-th bit of b as 0.
        }
        else // (Xi == 1 && Ai == 1)
        {
            Console.WriteLine("Not Possible");
            return;
        }
    }
 
    Console.WriteLine("a = " + a +"\nb = " + b);
}
 
// Driver function
    public static void Main() {
        long S = 17, X = 13;
        compute(S, X);
    }
}
// This code is contributed by RAJPUT-JI

JavaScript

// JavaScript program to find two numbers with
// given Sum and XOR such that value of
// first number is minimum.
 
 
// Function that takes in the sum and XOR
// of two numbers and generates the two
// numbers such that the value of X is
// minimized
function compute(S, X)
{
    var A = Math.floor((S - X) / 2);
    var a = 0;
    var b = 0;
 
    // Traverse through all bits
    for (var i = 0; i < 64; i++)
    {
        var Xi = (X & (1 << i));
        var Ai = (A & (1 << i));
        if (Xi == 0 && Ai == 0)
        {
            // Let us leave bits as 0.
            continue;
        }
             
        else if (Xi == 0 && Ai > 0)
        {
            a = ((1 << i) | a);
            b = ((1 << i) | b);
        }
         
        else if (Xi > 0 && Ai == 0)
        {
            a = ((1 << i) | a);
            // We leave i-th bit of b as 0.
        }
 
        else
        {
        // (Xi == 1 and Ai == 1)
            console.log("Not Possible");
            return;
        }
    }
 
    console.log("a = " + a);
    console.log("b = " + b);
}
 
// Driver function
var S = 17;
var X = 13;
compute(S, X);
 
// This code is contributed by phasing17
 
Output
a = 15
b = 2

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *