Dada una array arr[] de longitud impar N que contiene enteros positivos. La tarea es encontrar un entero positivo X tal que, sumando X a todos los elementos de arr[] y luego tomando XOR de todos los elementos da 0 . Devuelve -1 si no existe tal X.
Ejemplos:
Entrada: arr[] = {2, 4, 5}
Salida: 1
Explicación: Las siguientes son las operaciones realizadas en arr[] para obtener el resultado deseado.
Agregar 1 a cada elemento en arr[] actualiza arr[] a arr[] = {3, 5, 6}
Ahora XOR de todos los elementos en arr[] es 3^5^6 = 0.
Por lo tanto, 1 es el requerido responder.Entrada: arr[] = {4, 5, 13}
Salida: -1
Explicación: No existe tal x para cumplir las condiciones deseadas.
Enfoque: XOR de número impar de 1 = 1, mientras que número par de 1 = 0. Esta idea se puede utilizar para resolver el problema dado. Siga los pasos que se mencionan a continuación:
- Inicialice la variable X = 0 .
- Las representaciones binarias de los elementos de la array se utilizarán para atravesar los elementos y determinar X .
- Comience a atravesar desde el bit 0 hasta el bit 63.
- Si en cualquier posición de bit, el número total de bits establecidos (1) de los elementos de la array es impar, sume esa potencia de 2 con X.
- Si después de completar la iteración hay un número impar de 1 en cualquier posición de bit, entonces no existe tal X. De lo contrario, imprima X como respuesta.
Vea las ilustraciones a continuación:
Ilustración:
Caso-1 (X posible): Tomar arr[] = { 2, 4, 5}
5to 4to 3ro 2do 1º 0 arr[0] 0 0 0 0 1 0 arr[1] 0 0 0 1 0 0 arr[2] 0 0 0 1 0 1 X 0 0 0 0 0 0
- Inicialmente, X = 0 0 0 0 0 0 , en la posición 0, los bits establecidos (1) son impares, por lo que para que los bits establecidos sean pares, invierta los bits en la posición 0. Entonces, para voltear los bits simplemente agregue (0 0 0 0 0 1) a todos los elementos de arr[] y en X.
- Ahora, la tabla se verá como la siguiente:
5to 4to 3ro 2do 1º 0 arr[0] 0 0 0 0 1 1 arr[1] 0 0 0 1 0 1 arr[2] 0 0 0 1 1 0 XOR 0 0 0 0 0 0 X 0 0 0 0 0 1
- Ahora, el XOR de (arr[0]+x) ^ ( arr[1]+x) ^ arr[2]+x) = 0, el resultado será 0. Entonces, imprima res = X.
Tomar lo siguiente cuando no sea posible X
Caso-2: Tome el ejemplo: arr[] = { 4, 5, 13 }
5to 4to 3ro 2do 1º 0 arr[0] 0 0 0 1 0 0 arr[1] 0 0 0 1 0 1 arr[2] 0 0 1 1 0 1 XOR 0 0 1 1 0 0 X 0 0 0 0 0 0 XOR = Arr[0] ^ Arr[1] ^ Arr[2] = 1 1 0 0, Aquí hay un número impar de 1 en los bits 2 y 3.
- Entonces, agregue 2pow(2nd) a todos los elementos de arr y en X, luego nuevamente tomará el XOR , después de esto, los elementos se convierten en:
5to 4to 3ro 2do 1º 0 arr[0] 0 0 1 0 0 0 arr[1] 0 0 1 0 0 1 arr[2] 0 1 0 0 0 1 XOR 0 1 0 0 0 0 X 0 0 0 1 0 0 Si esto continúa, el 1 más a la izquierda en XOR continúa moviéndose hacia la izquierda.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find required result
long long solve(vector<long long>& a,
int n)
{
long long res = 0, j = 0, one = 1;
// For 64 Bit
while (j < 64) {
// j is traversing each bit
long long Xor = 0;
long long powerOf2 = one << j;
for (auto x : a)
Xor ^= x;
if (j == 63 && (Xor & powerOf2))
return -1;
if (Xor & powerOf2) {
res += powerOf2;
for (int i = 0; i < n; i++)
a[i] += powerOf2;
}
j++;
}
return res;
}
// Driver Code
int main()
{
// Size of arr[]
int N = 3;
vector<long long> arr = { 2, 4, 5 };
cout << solve(arr, N) << '\n';
return 0;
}
Java
// Java program for above approach
class GFG{
// Function to find required result
static long solve(int[] a,
int n)
{
long res = 0, j = 0, one = 1;
// For 64 Bit
while (j < 64)
{
// j is traversing each bit
long Xor = 0;
long powerOf2 = one << j;
for (int x : a)
Xor ^= x;
if (j == 63 && (Xor & powerOf2)!=0)
return -1;
if ((Xor & powerOf2)!=0) {
res += powerOf2;
for (int i = 0; i < n; i++)
a[i] += powerOf2;
}
j++;
}
return res;
}
// Driver Code
public static void main(String[] args)
{
// Size of arr[]
int N = 3;
int[] arr = { 2, 4, 5 };
System.out.print(solve(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# python program for above approach # Function to find required result def solve(a, n): res = 0 j = 0 one = 1 # For 64 Bit while (j < 64): # j is traversing each bit Xor = 0 powerOf2 = one << j for x in a: Xor ^= x if (j == 63 and (Xor & powerOf2)): return -1 if (Xor & powerOf2): res += powerOf2 for i in range(0, n): a[i] += powerOf2 j += 1 return res # Driver Code if __name__ == "__main__": # Size of arr[] N = 3 arr = [2, 4, 5] print(solve(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program for above approach
using System;
class GFG
{
// Function to find required result
static long solve(int[] a, int n)
{
int res = 0, j = 0, one = 1;
// For 64 Bit
while (j < 64)
{
// j is traversing each bit
long Xor = 0;
long powerOf2 = one << j;
foreach (int x in a)
Xor ^= x;
if (j == 63 && (Xor & powerOf2) != 0)
return -1;
if ((Xor & powerOf2) != 0)
{
res += (int)powerOf2;
for (int i = 0; i < n; i++)
a[i] += (int)powerOf2;
}
j++;
}
return res;
}
// Driver Code
public static void Main()
{
// Size of arr[]
int N = 3;
int[] arr = { 2, 4, 5 };
Console.Write(solve(arr, N));
}
}
// This code is contributed by gfgking
Javascript
<script>
// JavaScript program for above approach
// Function to find required result
function solve(a, n)
{
let res = 0, j = 0, one = 1;
// For 64 Bit
while (j < 64)
{
// j is traversing each bit
let Xor = 0;
let powerOf2 = one << j;
for(let x of a)
Xor ^= x;
if (j == 63 && (Xor & powerOf2))
return -1;
if (Xor & powerOf2)
{
res += powerOf2;
for(let i = 0; i < n; i++)
a[i] += powerOf2;
}
j++;
}
return res;
}
// Driver Code
// Size of arr[]
let N = 3;
let arr = [ 2, 4, 5 ];
document.write(solve(arr, N) + '<br>');
// This code is contributed by Potta Lokesh
</script>
1
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por madhav_mohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA