Dada una array arr[] en la que se da XOR de cada 2 elementos consecutivos de la array original, es decir, si el número total de elementos en la array original es 
entonces el tamaño de esta array XOR sería n-1. También se proporciona el primer elemento de la array original. La tarea es encontrar el resto de n-1 elementos de la array original.
- Sean a, b, c, d, e, f los elementos originales, y se da el xor de cada 2 elementos consecutivos, es decir a^b = k1 , b ^ c = k2 , c ^ d = k3 , d ^ e = k4 , e ^ f = k5 (donde k1, k2, k3, k4, k5 son los elementos que nos dan junto con el primer elemento a ), y tenemos que encontrar el valor de b, c, d, e, F. _
Ejemplos:
Input : arr[] = {13, 2, 6, 1}, a = 5
Output : 5 8 10 12 13
5^8=13, 8^10=2, 10^12=6, 12^13=1
Input : arr[] = {12, 5, 26, 7}, a = 6
Output : 6 10 15 21 18
Enfoque: podemos encontrar todos los elementos uno por uno con la ayuda de 
(primeros elementos), y para encontrar el siguiente elemento, es decir 
, tenemos que xor a por arr[0], de manera similar para 
xor arr[1] con b y así sucesivamente .
Esto funciona siguiendo las propiedades de XOR como se indica a continuación:
- XOR de un número a sí mismo es cero.
- XOR de un número con cero dado el propio número.
Entonces, como arr[0] contiene a^b . Por lo tanto,
a ^ arr[0] = a ^ a ^ b
= 0 ^ b
= b
De manera similar, arr[i] contiene XOR de a i y a i+1 . Por lo tanto,
ai ^ arr[i] = ai ^ ai ^ ai+1
= 0 ^ ai+1
= ai+1
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the array elements
// using XOR of consecutive elements
#include <bits/stdc++.h>
using namespace std;
// Function to find the array elements
// using XOR of consecutive elements
void getElements(int a, int arr[], int n)
{
// array to store the original
// elements
int elements[n + 1];
// first element a i.e elements[0]=a
elements[0] = a;
for (int i = 0; i < n; i++) {
/* To get the next elements we have to calculate
xor of previous elements with given xor of 2
consecutive elements.
e.g. if a^b=k1 so to get b xor a both side.
b = k1^a
*/
elements[i + 1] = arr[i] ^ elements[i];
}
// Printing the original array elements
for (int i = 0; i < n + 1; i++)
cout << elements[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 13, 2, 6, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int a = 5;
getElements(a, arr, n);
return 0;
}
Java
// Java program to find the array elements
// using XOR of consecutive elements
import java.io.*;
class GFG {
// Function to find the array elements
// using XOR of consecutive elements
static void getElements(int a, int arr[], int n)
{
// array to store the original
// elements
int elements[] = new int[n + 1];
// first element a i.e elements[0]=a
elements[0] = a;
for (int i = 0; i < n; i++) {
/* To get the next elements we have to calculate
xor of previous elements with given xor of 2
consecutive elements.
e.g. if a^b=k1 so to get b xor a both side.
b = k1^a
*/
elements[i + 1] = arr[i] ^ elements[i];
}
// Printing the original array elements
for (int i = 0; i < n + 1; i++)
System.out.print( elements[i] + " ");
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 13, 2, 6, 1 };
int n = arr.length;
int a = 5;
getElements(a, arr, n);
}
}
// This code is contributed by anuj_67..
Python3
# Python3 program to find the array # elements using xor of consecutive elements # Function to find the array elements # using XOR of consecutive elements def getElements(a, arr, n): # array to store the original elements elements = [1 for i in range(n + 1)] # first elements a i.e elements[0]=a elements[0] = a for i in range(n): # To get the next elements we have to # calculate xor of previous elements # with given xor of 2 consecutive elements. # e.g. if a^b=k1 so to get b xor a both side. # b = k1^a elements[i + 1] = arr[i] ^ elements[i] # Printing the original array elements for i in range(n + 1): print(elements[i], end = " ") # Driver code arr = [13, 2, 6, 1] n = len(arr) a = 5 getElements(a, arr, n) # This code is contributed by Mohit Kumar
C#
// C# program to find the array elements
// using XOR of consecutive elements
using System;
class GFG {
// Function to find the array elements
// using XOR of consecutive elements
static void getElements(int a, int []arr, int n)
{
// array to store the original
// elements
int []elements = new int[n + 1];
// first element a i.e elements[0]=a
elements[0] = a;
for (int i = 0; i < n; i++) {
/* To get the next elements we have to calculate
xor of previous elements with given xor of 2
consecutive elements.
e.g. if a^b=k1 so to get b xor a both side.
b = k1^a
*/
elements[i + 1] = arr[i] ^ elements[i];
}
// Printing the original array elements
for (int i = 0; i < n + 1; i++)
Console.Write( elements[i] + " ");
}
// Driver Code
public static void Main () {
int []arr = { 13, 2, 6, 1 };
int n = arr.Length;
int a = 5;
getElements(a, arr, n);
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP program to find the array elements
// using XOR of consecutive elements
// Function to find the array elements
// using XOR of consecutive elements
function getElements($a, &$arr, &$n)
{
// array to store the original
// elements
// first element a i.e elements[0]=a
$elements[0] = $a;
for ($i = 0; $i < $n; $i++)
{
/* To get the next elements we have to
calculate xor of previous elements
with given xor of 2 consecutive elements.
e.g. if a^b=k1 so to get b xor a both side.
b = k1^a
*/
$elements[$i + 1] = $arr[$i] ^ $elements[$i];
}
// Printing the original array elements
for ($i = 0; $i < $n + 1; $i++)
{
echo($elements[$i] . " ");
}
}
// Driver Code
$arr = array(13, 2, 6, 1);
$n = sizeof($arr);
$a = 5;
getElements($a, $arr, $n);
// This code is contributed by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find the array elements
// using XOR of consecutive elements
// Function to find the array elements
// using XOR of consecutive elements
function getElements(a, arr, n)
{
// Array to store the original
// elements
let elements = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
elements[i] = 0;
}
// first element a i.e elements[0]=a
elements[0] = a;
for(let i = 0; i < n; i++)
{
/* To get the next elements we have to calculate
xor of previous elements with given xor of 2
consecutive elements.
e.g. if a^b=k1 so to get b xor a both side.
b = k1^a
*/
elements[i + 1] = arr[i] ^ elements[i];
}
// Printing the original array elements
for(let i = 0; i < n + 1; i++)
document.write( elements[i] + " ");
}
// Driver Code
let arr = [ 13, 2, 6, 1 ];
let n = arr.length;
let a = 5;
getElements(a, arr, n);
// This code is contributed by unknown2108
</script>
Producción:
5 8 10 12 13
Complejidad Temporal: O(N), ya que se ejecuta un bucle N veces.
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA