Dada una lista S que inicialmente contiene un solo valor 0 . A continuación se muestran las consultas Q de los siguientes tipos:
- 0 X : Insertar X en la lista
- 1 X : Para cada elemento A en S, reemplácelo por A XOR X.
La tarea es imprimir todos los elementos de la lista en orden creciente después de realizar las consultas Q dadas .
Ejemplos:
Entrada: Q[][] = { {0, 6}, {0, 3}, {0, 2}, {1, 4}, {1, 5} }
Salida: 1 2 3 7
Explicación:
[0] (valor inicial)
[0 6] (agregar 6 a la lista)
[0 6 3] (agregar 3 a la lista)
[0 6 3 2] (agregar 2 a la lista)
[4 2 7 6] (XOR cada elemento por 4)
[1 7 2 3] (XOR cada elemento por 5)
Por lo tanto, el orden ordenado después de realizar consultas es [1 2 3 7]Entrada: Q[][]= {{0, 2}, {1, 3}, {0, 5} }
Salida: 1 3 5
Explicación:
[0] (valor inicial)
[0 2] (añadir 2 a la lista )
[3 1] (XOR cada elemento por 3)
[3 1 5] (agregue 5 a la lista)
Por lo tanto, el orden ordenado después de realizar consultas es [1 3 5]
Enfoque ingenuo: el enfoque más simple para resolver el problema es:
- Inicialice una lista con 0 , luego recorra cada consulta y haga lo siguiente:
- Para el tipo de consulta 0, agregue el valor dado en la lista.
- Para el tipo de consulta 1, recorra la lista y actualice cada elemento con su respectivo Bitwise XOR con value .
- Después de todas las consultas realizadas, imprima la lista final en orden creciente.
Complejidad de Tiempo: O(N*Q), donde N es la longitud de la lista y Q es el número de consultas
Espacio Auxiliar: O(1)
Enfoque eficiente: es mucho más fácil procesar los números en orden inverso al realizar un seguimiento del XOR bit a bit acumulativo que funciona de derecha a izquierda. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable xor con 0.
- Repita la array de consultas de derecha a izquierda, agregue xor^value a la lista mientras el tipo de consulta es 0 ; de lo contrario, actualice xor con xor^value .
- Después de atravesar la consulta, agregue xor a la lista y ordene la lista final.
- Imprima la lista final después de las operaciones anteriores.
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;
#define N 5
#define M 2
// Function to return required list
// after performing all the queries
list<int> ConstructList(int Q[N][M])
{
// Store cumulative Bitwise XOR
int xr = 0;
// Initialize final list to return
list<int> ans;
// Perform each query
for (int i = N - 1; i >= 0; i--)
{
if (Q[i][0] == 0)
ans.push_back(Q[i][1] ^ xr);
else
xr ^= Q[i][1];
}
// The initial value of 0
ans.push_back(xr);
// Sort the list
ans.sort();
// Return final list
return ans;
}
// Driver Code
int main()
{
// Given Queries
int Q[N][M] = {{ 0, 6 }, { 0, 3 },
{ 0, 2 }, { 1, 4 },
{ 1, 5 }};
// Function Call
list<int> ans = ConstructList(Q);
for (auto it = ans.begin(); it != ans.end(); ++it)
cout << ' ' << *it;
}
// This code is contributed by gauravrajput1
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to return required list
// after performing all the queries
static List<Integer> ConstructList(int[][] Q)
{
// Store cumulative Bitwise XOR
int xor = 0;
// Initialize final list to return
List<Integer> ans = new ArrayList<>();
// Perform each query
for (int i = Q.length - 1; i >= 0; i--) {
if (Q[i][0] == 0)
ans.add(Q[i][1] ^ xor);
else
xor ^= Q[i][1];
}
// The initial value of 0
ans.add(xor);
// Sort the list
Collections.sort(ans);
// Return final list
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given Queries
int[][] Q = {
{ 0, 6 }, { 0, 3 }, { 0, 2 },
{ 1, 4 }, { 1, 5 }
};
// Function Call
System.out.println(ConstructList(Q));
}
}
Python3
# Python3 program for the above approach # Function to return required list # after performing all the queries def ConstructList(Q): # Store cumulative Bitwise XOR xor = 0 # Initialize final list to return ans = [] # Perform each query for i in range(len(Q) - 1, -1, -1): if(Q[i][0] == 0): ans.append(Q[i][1] ^ xor) else: xor ^= Q[i][1] # The initial value of 0 ans.append(xor) # Sort the list ans.sort() # Return final list return ans # Driver Code # Given Queries Q = [ [0, 6], [0, 3], [0, 2], [1, 4], [1, 5] ] # Function call print(ConstructList(Q)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return required list
// after performing all the queries
static List<int> ConstructList(int[,] Q)
{
// Store cumulative Bitwise XOR
int xor = 0;
// Initialize readonly list to return
List<int> ans = new List<int>();
// Perform each query
for (int i = Q.GetLength(0) - 1; i >= 0; i--)
{
if (Q[i, 0] == 0)
ans.Add(Q[i, 1] ^ xor);
else
xor ^= Q[i, 1];
}
// The initial value of 0
ans.Add(xor);
// Sort the list
ans.Sort();
// Return readonly list
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given Queries
int[,] Q = {{ 0, 6 }, { 0, 3 }, { 0, 2 },
{ 1, 4 }, { 1, 5 }};
// Function Call
foreach( int i in ConstructList(Q))
Console.Write(i + ", ");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
var N = 5
var M = 2
// Function to return required list
// after performing all the queries
function ConstructList(Q)
{
// Store cumulative Bitwise XOR
var xr = 0;
// Initialize final list to return
var ans = [];
// Perform each query
for (var i = N - 1; i >= 0; i--)
{
if (Q[i][0] == 0)
ans.push(Q[i][1] ^ xr);
else
xr ^= Q[i][1];
}
// The initial value of 0
ans.push(xr);
// Sort the list
ans.sort((a,b)=>a-b);
// Return final list
return ans;
}
// Driver Code
// Given Queries
var Q = [[ 0, 6 ], [ 0, 3 ],
[ 0, 2 ], [ 1, 4 ],
[ 1, 5 ]];
// Function Call
var ans = ConstructList(Q);
ans.forEach(element => {
document.write(" "+element);
});
// This code is contributed by famously.
</script>
[1, 2, 3, 7]
Complejidad de tiempo: O(Q * log(Q)) , donde Q es el número de consultas.
Espacio auxiliar: O(N) , donde N es el número de elementos de la lista resultante.