Dados dos enteros positivos S y X que representan la suma y Bitwise XOR de todos los elementos de una array arr[] . La tarea es encontrar los elementos de la array arr[] . Si no se puede generar tal array, imprima -1.
Ejemplos:
Entrada: Sum = 4, Xor = 2
Salida: {3, 1}
Explicación:
La suma de 1 y 3 es 4.
Bitwise XOR de 1 y 3 es 2.
Entrada: Sum = 5, Xor = 8
Salida: -1
Explicación:
No existe tal array.
Planteamiento: Se puede probar que la longitud máxima del arreglo será como máximo 3. Consideremos los siguientes casos:
- Caso 1: si la Suma y el XOR bit a bit dados son iguales y distintos de cero, entonces, ese elemento será el único elemento de la array requerida.
- Caso 2: para Sum desigual y Bitwise XOR, la longitud de array más corta puede ser 2 o 3.
Si Bitwise XOR y Sum son a y b respectivamente, entonces la array más corta puede ser {a, (b – a)/2 , (ba)/2 } usando las siguientes dos propiedades de XOR:- a X o 0 = a
- a X o a = 0
- Caso 3: Cuando la longitud de la array puede ser 2.
La array que tomamos en el caso anterior se puede reducir a dos elementos si es posible.
Una fórmula importante útil aquí es: –
p + q = (p ^ q) + 2*(p & q)
Sustituyendo los valores de sum y xor en la fórmula anterior obtenemos una relación muy útil.
b = a + 2*(p & q)
(p & q) = (ba)/2
Del caso anterior,
x = (ba)/2 = (p & q)
Entonces, ahora veamos alguna relación entre a (dado xor) y x ((ba)/2).
p q a=(p^q) x=(p&q) a&x 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0
- Nota: p y q representan todos los 32 bits correspondientes de dos números en una array.
Es importante tener en cuenta que si a & x se vuelve cero , entonces a + x = a ^ x , lo que significa que la array se reducirá a {a+x, x} porque a+x = a^x . A partir de la fórmula anterior, que aún puede conducir a XOR general como a, y la suma seguirá siendo b ya que x es (ba)/2.
- Caso 4: el único caso que queda es verificar si existe una array o no. En este caso, solo hay dos condiciones para verificar como:
- Si Bitwise XOR es mayor que la suma.
- Si sum y xor tienen paridades diferentes, es decir, uno es par y el otro es impar.
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 array
void findArray(int sum, int xorr)
{
// array not possible
if (xorr > sum
|| sum % 2 != xorr % 2) {
cout << "No Array Possible\n";
return;
}
// Array possible with exactly 1
// or no element
if (sum == xorr) {
if (sum == 0)
cout << "Array is empty"
<< " with size 0\n";
else
cout << "Array size is "
<< 1
<< "\n Array is "
<< sum << "\n";
return;
}
int mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr & mid == 1) {
cout << "Array size is "
<< 3 << "\n";
cout << "Array is "
<< xorr << " "
<< mid << " "
<< mid << "\n";
}
else {
cout << "Array size is "
<< 2 << "\n";
cout << "Array is "
<< (xorr + mid)
<< " "
<< mid << "\n";
}
}
// Driver Code
int main()
{
// Given sum and value
// of Bitwise XOR
int sum = 4, xorr = 2;
// Function Call
findArray(sum, xorr);
cout << "\n";
return 0;
}
Java
// Java program implementation
// of the approach
import java.util.*;
import java.io.*;
class GFG{
// Function to find array
static void findArray(int sum, int xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2)
{
System.out.println("No Array Possible");
return;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0)
System.out.println("Array is empty " +
"with size 0");
else
System.out.println("Array size is " + 1);
System.out.println("Array is " + sum);
return;
}
int mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1)
{
System.out.println("Array size is " + 3);
System.out.println("Array is " + xorr +
" " + mid + " " + mid);
}
else
{
System.out.println("Array size is " + 2);
System.out.println("Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
public static void main(String[] args)
{
// Given sum and value
// of Bitwise XOR
int sum = 4, xorr = 2;
// Function call
findArray(sum, xorr);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
# Function to find array
def findArray(_sum, xorr):
# Array not possible
if (xorr > _sum or
_sum % 2 != xorr % 2):
print("No Array Possible")
return
# Array possible with exactly 1
# or no element
if (_sum == xorr):
if (_sum == 0):
print("Array is empty",
" with size 0")
else:
print("Array size is", 1)
print("Array is", _sum)
return
mid = (_sum - xorr) // 2
# Checking array with two
# elements possible or not.
if (xorr & mid == 1):
print("Array size is", 3)
print("Array is", xorr, mid, mid)
else:
print("Array size is", 2)
print("Array is" ,(xorr + mid), mid)
# Driver Code
# Given sum and value
# of Bitwise XOR
_sum = 4
xorr = 2
# Function Call
findArray(_sum, xorr)
# This code is contributed by divyamohan123
C#
// C# program implementation
// of the approach
using System;
class GFG{
// Function to find array
static void findArray(int sum, int xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2)
{
Console.WriteLine("No Array Possible");
return;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0)
Console.WriteLine("Array is empty " +
"with size 0");
else
Console.WriteLine("Array size is " + 1);
Console.WriteLine("Array is " + sum);
return;
}
int mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1)
{
Console.WriteLine("Array size is " + 3);
Console.WriteLine("Array is " + xorr +
" " + mid + " " + mid);
}
else
{
Console.WriteLine("Array size is " + 2);
Console.WriteLine("Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
public static void Main()
{
// Given sum and value
// of Bitwise XOR
int sum = 4, xorr = 2;
// Function call
findArray(sum, xorr);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program implementation
// of the approach
// Function to find array
function findArray(sum, xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2)
{
System.out.println("No Array Possible");
return;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0)
document.write("Array is empty " +
"with size 0");
else
document.write("Array size is " + 1);
document.write(" Array is " + sum);
return;
}
var mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1)
{
document.write("Array size is " + 3);
document.write("Array is " + xorr +
" " + mid + " " + mid);
}
else
{
document.write("Array size is " + 2);
document.write("<br>")
document.write("Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
// Given sum and value
// of Bitwise XOR
var sum = 4, xorr = 2;
// Function call
findArray(sum, xorr);
// This code is contributed by Khushboogoyal499
</script>
Producción:
Array size is 2 Array is 3 1
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sarthak_eddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA