Dada una secuencia arr[] de N-1 elementos que es xor de todos los pares adyacentes en una array, la tarea es encontrar esa array original a partir de arr[] .
Nota: Se da que el N siempre es impar y arr[] contiene la permutación de N número natural .
Ejemplos:
Entrada: arr[] = {3, 1}
Salida: 1 2 3
Explicación:
El XOR de la array de salida conducirá a la array dada que es:
1 ^ 2 = 3
2 ^ 3 = 1
Entrada: arr[] = { 7, 5, 3, 7}
Salida: 3 4 1 2 5
Explicación:
El XOR de la array de salida conducirá a la array dada que es:
3 ^ 4 = 7
4 ^ 1 = 5
1 ^ 2 = 3
2 ^ 5 = 7
Acercarse:
- La idea es encontrar el XOR de todos los elementos del 1 al N y el xor de los elementos adyacentes del arreglo dado para encontrar el último elemento del arreglo esperado.
- Como el XOR de elementos adyacentes contendrá todos los elementos excepto el último elemento, entonces el XOR de este con todos los números del 1 al N dará el último elemento de la permutación esperada.
Por ejemplo:
Let's the expected array be - {a, b, c, d, e}
Then the XOR array for this array will be -
{a^b, b^c, c^d, d^e}
Now XOR of all the element from 1 to N -
xor_all => a ^ b ^ c ^ d ^ e
XOR of the adjacent elements -
xor_adjacent => ((a ^ b) ^ (c ^ d))
Now the XOR of the both the array will be the
last element of the expected permutation
=> (a ^ b ^ c ^ d ^ e) ^ ((a ^ b) ^ (c ^ d))
=> As all elements are in pair except the last element.
=> (a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ e)
=> (0 ^ 0 ^ 0 ^ 0 ^ e)
=> e
- Ahora para el resto del elemento, continuamente, en xor de este último elemento obtendremos el último segundo elemento, es decir, d .
- Repetidamente, actualice el último elemento y finalmente obtenga el primer elemento, es decir, un .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Array from the XOR array
// of the adjacent elements of array
#include <bits/stdc++.h>
using namespace std;
// XOR of all elements from 1 to N
int xor_all_elements(int n)
{
switch (n & 3) {
case 0:
return n;
case 1:
return 1;
case 2:
return n + 1;
case 3:
return 0;
}
}
// Function to find the Array
// from the XOR Array
vector<int> findArray(int xorr[], int n)
{
// Take a vector to store
// the permutation
vector<int> arr;
// XOR of N natural numbers
int xor_all = xor_all_elements(n);
int xor_adjacent = 0;
// Loop to find the XOR of
// adjacent elements of the XOR Array
for (int i = 0; i < n - 1; i += 2) {
xor_adjacent = xor_adjacent ^ xorr[i];
}
int last_element = xor_all ^ xor_adjacent;
arr.push_back(last_element);
// Loop to find the other
// elements of the permutation
for (int i = n - 2; i >= 0; i--) {
// Finding the next and next elements
last_element = xorr[i] ^ last_element;
arr.push_back(last_element);
}
return arr;
}
// Driver Code
int main()
{
vector<int> arr;
int xorr[] = { 7, 5, 3, 7 };
int n = 5;
arr = findArray(xorr, n);
// Required Permutation
for (int i = n - 1; i >= 0; i--) {
cout << arr[i] << " ";
}
}
Java
// Java implementation to find the
// Array from the XOR array
// of the adjacent elements of array
import java.util.*;
class GFG{
// XOR of all elements from 1 to N
static int xor_all_elements(int n)
{
switch (n & 3) {
case 0:
return n;
case 1:
return 1;
case 2:
return n + 1;
}
return 0;
}
// Function to find the Array
// from the XOR Array
static Vector<Integer> findArray(int xorr[], int n)
{
// Take a vector to store
// the permutation
Vector<Integer> arr = new Vector<Integer>();
// XOR of N natural numbers
int xor_all = xor_all_elements(n);
int xor_adjacent = 0;
// Loop to find the XOR of
// adjacent elements of the XOR Array
for (int i = 0; i < n - 1; i += 2) {
xor_adjacent = xor_adjacent ^ xorr[i];
}
int last_element = xor_all ^ xor_adjacent;
arr.add(last_element);
// Loop to find the other
// elements of the permutation
for (int i = n - 2; i >= 0; i--)
{
// Finding the next and next elements
last_element = xorr[i] ^ last_element;
arr.add(last_element);
}
return arr;
}
// Driver Code
public static void main(String[] args)
{
Vector<Integer> arr = new Vector<Integer>();
int xorr[] = { 7, 5, 3, 7 };
int n = 5;
arr = findArray(xorr, n);
// Required Permutation
for (int i = n - 1; i >= 0; i--)
{
System.out.print(arr.get(i)+ " ");
}
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to find the # Array from the XOR array # of the adjacent elements of array # XOR of all elements from 1 to N def xor_all_elements(n): if n & 3 == 0: return n elif n & 3 == 1: return 1 elif n & 3 == 2: return n + 1 else: return 0 # Function to find the Array # from the XOR Array def findArray(xorr, n): # Take a vector to store # the permutation arr = [] # XOR of N natural numbers xor_all = xor_all_elements(n) xor_adjacent = 0 # Loop to find the XOR of # adjacent elements of the XOR Array for i in range(0, n - 1, 2): xor_adjacent = xor_adjacent ^ xorr[i] last_element = xor_all ^ xor_adjacent arr.append(last_element) # Loop to find the other # elements of the permutation for i in range(n - 2, -1, -1): # Finding the next and next elements last_element = xorr[i] ^ last_element arr.append(last_element) return arr # Driver Code xorr = [7, 5, 3, 7] n = 5 arr = findArray(xorr, n) # Required Permutation for i in range(n - 1, -1, -1): print(arr[i], end=" ") # This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// Array from the XOR array
// of the adjacent elements of array
using System;
using System.Collections.Generic;
class GFG{
// XOR of all elements from 1 to N
static int xor_all_elements(int n)
{
switch (n & 3) {
case 0:
return n;
case 1:
return 1;
case 2:
return n + 1;
}
return 0;
}
// Function to find the Array
// from the XOR Array
static List<int> findArray(int []xorr, int n)
{
// Take a vector to store
// the permutation
List<int> arr = new List<int>();
// XOR of N natural numbers
int xor_all = xor_all_elements(n);
int xor_adjacent = 0;
// Loop to find the XOR of
// adjacent elements of the XOR Array
for (int i = 0; i < n - 1; i += 2) {
xor_adjacent = xor_adjacent ^ xorr[i];
}
int last_element = xor_all ^ xor_adjacent;
arr.Add(last_element);
// Loop to find the other
// elements of the permutation
for (int i = n - 2; i >= 0; i--)
{
// Finding the next and next elements
last_element = xorr[i] ^ last_element;
arr.Add(last_element);
}
return arr;
}
// Driver Code
public static void Main(String[] args)
{
List<int> arr = new List<int>();
int []xorr = { 7, 5, 3, 7 };
int n = 5;
arr = findArray(xorr, n);
// Required Permutation
for (int i = n - 1; i >= 0; i--)
{
Console.Write(arr[i]+ " ");
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the
// Array from the XOR array
// of the adjacent elements of array
// XOR of all elements from 1 to N
function xor_all_elements(n)
{
switch (n & 3) {
case 0:
return n;
case 1:
return 1;
case 2:
return n + 1;
case 3:
return 0;
}
}
// Function to find the Array
// from the XOR Array
function findArray(xorr, n)
{
// Take a vector to store
// the permutation
let arr = [];
// XOR of N natural numbers
let xor_all = xor_all_elements(n);
let xor_adjacent = 0;
// Loop to find the XOR of
// adjacent elements of the XOR Array
for (let i = 0; i < n - 1; i += 2) {
xor_adjacent = xor_adjacent ^ xorr[i];
}
let last_element = xor_all ^ xor_adjacent;
arr.push(last_element);
// Loop to find the other
// elements of the permutation
for (let i = n - 2; i >= 0; i--) {
// Finding the next and next elements
last_element = xorr[i] ^ last_element;
arr.push(last_element);
}
return arr;
}
// Driver Code
let arr = [];
let xorr = [ 7, 5, 3, 7 ];
let n = 5;
arr = findArray(xorr, n);
// Required Permutation
for (let i = n - 1; i >= 0; i--) {
document.write(arr[i] + " ");
}
</script>
Producción:
3 4 1 2 5
Análisis de rendimiento:
- Complejidad de tiempo: en el enfoque anterior, iteramos sobre toda la array xor para encontrar el XOR de los elementos adyacentes, luego la complejidad en el peor de los casos será O (N)
- Complejidad espacial: en el enfoque anterior, se usa una array vectorial para almacenar la permutación de los números de 1 a N , luego la complejidad espacial será O (N)