Dada una array q[] de consultas XOR de tamaño N (N es un múltiplo de 4) que describen una array del mismo tamaño de la siguiente manera:
q[0 – 3] describe arr[0 – 3], q[4 – 7] describe arr[4 – 7], y así sucesivamente…
Si arr[0 – 3] = {a1, a2, a3, a4} entonces
q[0 – 3] = {un 1 ⊕ un 2 ⊕ un 3 , un 1 ⊕ un 2 ⊕ un 4 , un 1 ⊕ un 3 ⊕ un 4 , un 2 ⊕ un 3 ⊕ un 4 }
La tarea es encontrar los valores de la array original arr[] cuando solo se da q[] .
Ejemplo:
Entrada: q[] = {4, 1, 7, 0}
Salida: 2 5 3 6
a 1 ⊕ a 2 ⊕ a 3 = 4 ⊕ 1 ⊕ 7 = 2
a 1 ⊕ a 2 ⊕ a 4 = 4 ⊕ 1 ⊕ 0 = 5
a 1 ⊕ a 3 ⊕ a 4 = 4 ⊕ 7 ⊕ 0 = 3
a 2 ⊕ a 3 ⊕ a 4 = 1 ⊕ 7 ⊕ 0 = 6
Entrada: q[] = {4, 1, 7, 0, 8, 5, 1, 4}
Salida: 2 5 3 6 12 9 13 0
Enfoque: A partir de las propiedades de xor, a ⊕ a = 0 ya ⊕ 0 = a .
(a ⊕ b ⊕ c) ⊕ (b ⊕ c ⊕ d) = a ⊕ d (As (b ⊕ c) ⊕ (b ⊕ c) = 0)
Entonces dividiremos el arreglo en grupos de 4 elementos y para cada grupo( a, b, c, d) nos darán
resultados de las siguientes consultas:
- un ⊕ segundo ⊕ c
- un ⊕ segundo ⊕ re
- un ⊕ c ⊕ re
- segundo ⊕ c ⊕ re
Como (a ⊕ b ⊕ c) ⊕ (b ⊕ c ⊕ d) = a ⊕ d ,
usando esto (a ⊕ d) podemos obtener b y c de la consulta 2 y 3 de la siguiente manera:
(a ⊕ b ⊕ d ) ⊕ (a ⊕ d) = b
(a ⊕ c ⊕ d) ⊕ (a ⊕ d) = c
Entonces usando b y c podemos obtener a de la consulta 1 y d de la consulta 4 de la siguiente manera:
(a ⊕ b ⊕ c) ⊕ (b) ⊕ (c) = a
(b ⊕ c ⊕ d) ⊕ (b) ⊕ (c) = d
Este proceso se repetirá (iterativamente) para todos los grupos de 4 elementos y obtendremos elementos de todos los índices (ej. (a, a
, a
, a
) luego (a
, a
, a
, a
) etc.)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to print the contents of the array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Function to find the required array
void findArray(int q[], int n)
{
int arr[n], ans;
for (int k = 0, j = 0; j < n / 4; j++) {
ans = q[k] ^ q[k + 3];
arr[k + 1] = q[k + 1] ^ ans;
arr[k + 2] = q[k + 2] ^ ans;
arr[k] = q[k] ^ ((arr[k + 1]) ^ (arr[k + 2]));
arr[k + 3] = q[k + 3] ^ (arr[k + 1] ^ arr[k + 2]);
k += 4;
}
// Print the array
printArray(arr, n);
}
// Driver code
int main()
{
int q[] = { 4, 1, 7, 0 };
int n = sizeof(q) / sizeof(q[0]);
findArray(q, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Utility function to print
// the contents of the array
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Function to find the required array
static void findArray(int []q, int n)
{
int ans;
int []arr = new int[n];
for (int k = 0, j = 0;
j < n / 4; j++)
{
ans = q[k] ^ q[k + 3];
arr[k + 1] = q[k + 1] ^ ans;
arr[k + 2] = q[k + 2] ^ ans;
arr[k] = q[k] ^ ((arr[k + 1]) ^
(arr[k + 2]));
arr[k + 3] = q[k + 3] ^ (arr[k + 1] ^
arr[k + 2]);
k += 4;
}
// Print the array
printArray(arr, n);
}
// Driver code
public static void main(String args[])
{
int []q = { 4, 1, 7, 0 };
int n = q.length;
findArray(q, n);
}
}
// This code is contributed
// by Akanksha Rai
Python3
# Python 3 implementation of the approach # Utility function to print the # contents of the array def printArray(arr, n): for i in range(n): print(arr[i], end = " ") # Function to find the required array def findArray(q, n): arr = [None] * n k = 0 for j in range(int(n / 4)): ans = q[k] ^ q[k + 3] arr[k + 1] = q[k + 1] ^ ans arr[k + 2] = q[k + 2] ^ ans arr[k] = q[k] ^ ((arr[k + 1]) ^ (arr[k + 2])) arr[k + 3] = q[k + 3] ^ (arr[k + 1] ^ arr[k + 2]) k += 4 # Print the array printArray(arr, n) # Driver code if __name__ == '__main__': q = [4, 1, 7, 0] n = len(q) findArray(q, n) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to print
// the contents of the array
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Function to find the required array
static void findArray(int []q, int n)
{
int ans;
int []arr = new int[n] ;
for (int k = 0, j = 0; j < n / 4; j++)
{
ans = q[k] ^ q[k + 3];
arr[k + 1] = q[k + 1] ^ ans;
arr[k + 2] = q[k + 2] ^ ans;
arr[k] = q[k] ^ ((arr[k + 1]) ^ (arr[k + 2]));
arr[k + 3] = q[k + 3] ^ (arr[k + 1] ^ arr[k + 2]);
k += 4;
}
// Print the array
printArray(arr, n);
}
// Driver code
public static void Main()
{
int []q = { 4, 1, 7, 0 };
int n = q.Length ;
findArray(q, n);
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Utility function to print
// the contents of the array
function printArray($arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo($arr[$i] ." ");
}
// Function to find the required array
function findArray($q, $n)
{
$ans;
$arr = array($n);
for ($k = 0, $j = 0; $j < $n / 4; $j++)
{
$ans = $q[$k] ^ $q[$k + 3];
$arr[$k + 1] = $q[$k + 1] ^ $ans;
$arr[$k + 2] = $q[$k + 2] ^ $ans;
$arr[$k] = $q[$k] ^ (($arr[$k + 1]) ^
($arr[$k + 2]));
$arr[$k + 3] = $q[$k + 3] ^ ($arr[$k + 1] ^
$arr[$k + 2]);
$k += 4;
}
// Print the array
printArray($arr, $n);
}
// Driver code
{
$q = array( 4, 1, 7, 0 );
$n = sizeof($q);
findArray($q, $n);
}
// This code is contributed
// by Code_Mech.
Javascript
<script>
// Javascript implementation
// of the approach
// Utility function to print the
// contents of the array
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to find the required array
function findArray(q, n)
{
let arr = new Array(n), ans;
for (let k = 0, j = 0; j <
parseInt(n / 4); j++)
{
ans = q[k] ^ q[k + 3];
arr[k + 1] = q[k + 1] ^ ans;
arr[k + 2] = q[k + 2] ^ ans;
arr[k] = q[k] ^ ((arr[k + 1]) ^
(arr[k + 2]));
arr[k + 3] = q[k + 3] ^ (arr[k + 1] ^
arr[k + 2]);
k += 4;
}
// Print the array
printArray(arr, n);
}
// Driver code
let q = [ 4, 1, 7, 0 ];
let n = q.length;
findArray(q, n);
</script>
2 5 3 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Vishwanath Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA