Dada una array de N (siempre una potencia de 2) elementos y Q consultas.
Cada consulta consta de dos elementos, un índice y un valor … Necesitamos escribir un programa que asigne un valor a un índice e imprima el único elemento que queda después de realizar las siguientes operaciones para cada consulta:
- En pasos alternativos, realice operaciones OR bit a bit y operaciones XOR bit a bit en los elementos adyacentes.
- En la primera iteración, seleccione, seleccione n/2 pares moviéndose de izquierda a derecha y haga un OR bit a bit de todos los valores de par. En la segunda iteración, seleccione (n/2)/2 pares sobrantes y haga un XOR bit a bit en ellos. En la tercera iteración, seleccione, seleccione ((n/2)/2)/2 pares sobrantes moviéndose de izquierda a derecha, y haga un OR bit a bit de todos los valores de par.
- Continúe con los pasos anteriores hasta que nos quede un solo elemento.
Ejemplos:
Input : n = 4 m = 2 arr = [1, 4, 5, 6] Queries- 1st: index=0 value=2 2nd: index=3 value=5 Output : 1 3 Explanation: 1st query: Assigning 2 to index 0, the sequence is now [2, 4, 5, 6]. 1st iteration: There are 4/2=2 pairs (2, 4) and (5, 6) 2 OR 4 gives 6, and 5 OR 6 gives us 7. So the sequence is now [6, 7]. 2nd iteration: There is 1 pair left now (6, 7) 6^7=1. Hence the last element left is 1 which is the answer to our first query. 2nd Query: Assigning 5 to index 3, the sequence is now [2, 4, 5, 5]. 1st iteration: There are 4/2=2 pairs (2, 4) and (5, 5) 2 OR 4 gives 6, and 5 OR 5 gives us 5. So the sequence is now [6, 5]. 2nd iteration: There is 1 pair left now (6, 5) 6^5=3. Hence the last element left is 3 which is the answer to our second query.
Enfoque ingenuo : el enfoque ingenuo es realizar cada paso hasta que nos quede un elemento. Usando un vector 2-D, almacenaremos los elementos resultantes que quedan después de cada paso. V[pasos-1][0..tamaño] da el número de elementos en el paso anterior. Si el número de paso es impar, realizamos una operación OR bit a bit, de lo contrario, se realiza una operación XOR bit a bit. Repita los pasos hasta que tengamos un sobrante con un elemento. El último elemento que queda será nuestra respuesta.
A continuación se muestra la implementación del enfoque ingenuo:
C++
// CPP program to print the Leftover element after // performing alternate Bitwise OR and Bitwise XOR // operations to the pairs. #include <bits/stdc++.h> using namespace std; #define N 1000 int lastElement(int a[],int n) { // count the step number int steps = 1; vector<int>v[N]; // if one element is there, it will be the answer if (n==1) return a[0]; // at first step we do a bitwise OR for (int i = 0 ; i < n ; i += 2) v[steps].push_back(a[i] | a[i+1]); // keep on doing bitwise operations till the // last element is left while (v[steps].size()>1) { steps += 1; // perform operations for (int i = 0 ; i < v[steps-1].size(); i+=2) { // if step is the odd step if (steps&1) v[steps].push_back(v[steps-1][i] | v[steps-1][i+1]); else // even step v[steps].push_back(v[steps-1][i] ^ v[steps-1][i+1]); } } // answer when one element is left return v[steps][0]; } // Driver Code int main() { int a[] = {1, 4, 5, 6}; int n = sizeof(a)/sizeof(a[0]); // 1st query int index = 0; int value = 2; a[0] = 2; cout << lastElement(a,n) << endl; // 2nd query index = 3; value = 5; a[index] = value; cout << lastElement(a,n) << endl; return 0; }
Java
// Java program to print the Leftover element // after performing alternate Bitwise OR and // Bitwise XOR operations to the pairs. import java.util.*; class GFG { static int N = 1000; static int lastElement(int a[], int n) { // count the step number int steps = 1; Vector<Integer> []v = new Vector[N]; for (int i = 0; i < N; i++) v[i] = new Vector<Integer>(); // if one element is there, // it will be the answer if (n == 1) return a[0]; // at first step we do a bitwise OR for (int i = 0 ; i < n ; i += 2) v[steps].add(a[i] | a[i + 1]); // keep on doing bitwise operations // till the last element is left while (v[steps].size() > 1) { steps += 1; // perform operations for (int i = 0; i < v[steps - 1].size(); i += 2) { // if step is the odd step if (steps % 2 == 1) v[steps].add(v[steps - 1].get(i) | v[steps - 1].get(i + 1)); else // even step v[steps].add(v[steps - 1].get(i) ^ v[steps - 1].get(i + 1)); } } // answer when one element is left return v[steps].get(0); } // Driver Code public static void main(String[] args) { int a[] = {1, 4, 5, 6}; int n = a.length; // 1st query int index = 0; int value = 2; a[0] = 2; System.out.println(lastElement(a, n)); // 2nd query index = 3; value = 5; a[index] = value; System.out.println(lastElement(a, n)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to print the Leftover element # after performing alternate Bitwise OR and # Bitwise XOR operations to the pairs. N = 1000 def lastElement(a, n): # count the step number steps = 1 v = [[] for i in range(n)] # if one element is there, it will be the answer if n == 1: return a[0] # at first step we do a bitwise OR for i in range(0, n, 2): v[steps].append(a[i] | a[i+1]) # keep on doing bitwise operations # till the last element is left while len(v[steps]) > 1: steps += 1 # perform operations for i in range(0, len(v[steps-1]), 2): # if step is the odd step if steps & 1: v[steps].append(v[steps-1][i] | v[steps-1][i+1]) else: # even step v[steps].append(v[steps-1][i] ^ v[steps-1][i+1]) # answer when one element is left return v[steps][0] # Driver Code if __name__ == "__main__": a = [1, 4, 5, 6] n = len(a) # 1st query index, value, a[0] = 0, 2, 2 print(lastElement(a,n)) # 2nd query index, value = 3, 5 value = 5 a[index] = value print(lastElement(a,n)) # This code is contributed by Rituraj Jain
C#
// C# program to print the Leftover element // after performing alternate Bitwise OR and // Bitwise XOR operations to the pairs. using System; using System.Collections.Generic; class GFG { static int N = 1000; static int lastElement(int []a, int n) { // count the step number int steps = 1; List<int> []v = new List<int>[N]; for (int i = 0; i < N; i++) v[i] = new List<int>(); // if one element is there, // it will be the answer if (n == 1) return a[0]; // at first step we do a bitwise OR for (int i = 0 ; i < n ; i += 2) v[steps].Add(a[i] | a[i + 1]); // keep on doing bitwise operations // till the last element is left while (v[steps].Count > 1) { steps += 1; // perform operations for (int i = 0; i < v[steps - 1].Count; i += 2) { // if step is the odd step if (steps % 2 == 1) v[steps].Add(v[steps - 1][i] | v[steps - 1][i + 1]); else // even step v[steps].Add(v[steps - 1][i] ^ v[steps - 1][i + 1]); } } // answer when one element is left return v[steps][0]; } // Driver Code public static void Main(String[] args) { int []a = {1, 4, 5, 6}; int n = a.Length; // 1st query int index = 0; int value = 2; a[0] = 2; Console.WriteLine(lastElement(a, n)); // 2nd query index = 3; value = 5; a[index] = value; Console.WriteLine(lastElement(a, n)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to print the Leftover element after // performing alternate Bitwise OR and Bitwise XOR // operations to the pairs. var N = 1000 function lastElement(a,n) { // count the step number var steps = 1; var v = Array.from(Array(N), ()=>Array(0)); // if one element is there, it will be the answer if (n==1) return a[0]; // at first step we do a bitwise OR for (var i = 0 ; i < n ; i += 2) v[steps].push(a[i] | a[i+1]); // keep on doing bitwise operations till the // last element is left while (v[steps].length>1) { steps += 1; // perform operations for (var i = 0 ; i < v[steps-1].length; i+=2) { // if step is the odd step if (steps&1) v[steps].push(v[steps-1][i] | v[steps-1][i+1]); else // even step v[steps].push(v[steps-1][i] ^ v[steps-1][i+1]); } } // answer when one element is left return v[steps][0]; } // Driver Code var a = [1, 4, 5, 6]; var n = a.length; // 1st query var index = 0; var value = 2; a[0] = 2; document.write( lastElement(a,n) + "<br>"); // 2nd query index = 3; value = 5; a[index] = value; document.write( lastElement(a,n)); </script>
Producción:
1 3
Complejidad de tiempo: O(N * 2 N )
Complejidad de espacio : O(N ^ 2)
Enfoque eficiente : El enfoque eficiente es utilizar un árbol de segmentos . A continuación se muestra el enfoque de árbol de segmentos completo utilizado para resolver el problema.
Construyendo el árbol
Las hojas del árbol de segmentos almacenarán la array de valores y sus padres almacenarán el OR de las hojas. Moviéndose hacia arriba en el árbol, con cada paso alternativo, el padre almacena XOR bit a bit o OR bit a bit entre el hijo izquierdo y derecho. En cada iteración impar, realizamos el OR bit a bit de los pares y , de manera similar, realizamos el XOR bit a bit de los pares en cada operación par . Entonces, el padre impar almacenará el OR bit a bit del hijo izquierdo y derecho. De manera similar, el padre con número par almacena el XOR bit a bit del hijo izquierdo y derecho. level[] es una array que almacena niveles de cada padre a partir de 1, para determinar si el par (hijo derecho e hijo izquierdo) debajo de él realiza una operación OR o una operación XOR.La raíz del árbol será nuestra respuesta a la secuencia dada después de cada operación de actualización.
.La imagen de arriba explica la construcción del árbol. Si la secuencia fue [1, 2, 3, 4, 5, 6, 7, 8], luego de 3 iteraciones, nos quedará 12, que es nuestra respuesta y se almacena en la raíz.
Consulta
de respuesta No es necesario reconstruir el árbol completo para realizar una operación de actualización. Para hacer una actualización, debemos encontrar una ruta desde la raíz hasta la hoja correspondiente y recalcular los valores solo para los padres que se encuentran en la ruta encontrada.
Nivel de padre:
usando DP en árboles , podemos almacenar fácilmente el nivel de cada padre. Inicialice el nivel de los Nodes hoja en 0 y siga agregando a medida que avanzamos hacia cada padre.
La relación de recurrencia para calcular el nivel de padre es:
nivel[padre] = nivel[hijo] + 1
Aquí, un hijo es 2*pos + 1 o 2*pos + 2
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to print the Leftover element after // performing alternate Bitwise OR and // Bitwise XOR operations to the pairs. #include <bits/stdc++.h> using namespace std; #define N 1000 // array to store the tree int tree[N]; // array to store the level of every parent int level[N]; // function to construct the tree void constructTree(int low, int high, int pos, int a[]) { if (low == high) { // level of child is always 0 level[pos] = 0; tree[pos] = a[high]; return; } int mid = (low + high) / 2; // recursive call constructTree(low, mid, 2 * pos + 1, a); constructTree(mid + 1, high, 2 * pos + 2, a); // increase the level of every parent, which is // level of child + 1 level[pos] = level[2 * pos + 1] + 1; // if the parent is at odd level, then do a // bitwise OR if (level[pos] & 1) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; // if the parent is at even level, then // do a bitwise XOR else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } // function that updates the tree void update(int low, int high, int pos, int index, int a[]) { // if it is a leaf and the leaf which is // to be updated if (low == high and low == index) { tree[pos] = a[low]; return; } // out of range if (index < low || index > high) return; // not a leaf then recurse if (low != high) { int mid = (low + high) / 2; // recursive call update(low, mid, 2 * pos + 1, index, a); update(mid + 1, high, 2 * pos + 2, index, a); // check if the parent is at odd or even level // and perform OR or XOR according to that if (level[pos] & 1) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } } // function that assigns value to a[index] // and calls update function to update the tree void updateValue(int index, int value, int a[], int n) { a[index] = value; update(0, n - 1, 0, index, a); } // Driver Code int main() { int a[] = { 1, 4, 5, 6 }; int n = sizeof(a) / sizeof(a[0]); // builds the tree constructTree(0, n - 1, 0, a); // 1st query int index = 0; int value = 2; updateValue(index, value, a, n); cout << tree[0] << endl; // 2nd query index = 3; value = 5; updateValue(index, value, a, n); cout << tree[0] << endl; return 0; }
Java
// java program to print the Leftover // element after performing alternate // Bitwise OR and Bitwise XOR operations // to the pairs. import java .io.*; public class GFG { static int N = 1000; // array to store the tree static int []tree = new int[N]; // array to store the level of // every parent static int []level = new int[N]; // function to construct the tree static void constructTree(int low, int high, int pos, int []a) { if (low == high) { // level of child is // always 0 level[pos] = 0; tree[pos] = a[high]; return; } int mid = (low + high) / 2; // recursive call constructTree(low, mid, 2 * pos + 1, a); constructTree(mid + 1, high, 2 * pos + 2, a); // increase the level of every parent, // which is level of child + 1 level[pos] = level[2 * pos + 1] + 1; // if the parent is at odd level, then // do a bitwise OR if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; // if the parent is at even level, then // do a bitwise XOR else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } // function that updates the tree static void update(int low, int high, int pos, int index, int []a) { // if it is a leaf and the leaf which is // to be updated if (low == high && low == index) { tree[pos] = a[low]; return; } // out of range if (index < low || index > high) return; // not a leaf then recurse if (low != high) { int mid = (low + high) / 2; // recursive call update(low, mid, 2 * pos + 1, index, a); update(mid + 1, high, 2 * pos + 2, index, a); // check if the parent is at odd or // even level and perform OR or XOR // according to that if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } } // function that assigns value to a[index] // and calls update function to update the // tree static void updateValue(int index, int value, int []a, int n) { a[index] = value; update(0, n - 1, 0, index, a); } // Driver Code static public void main (String[] args) { int []a = { 1, 4, 5, 6 }; int n = a.length;; // builds the tree constructTree(0, n - 1, 0, a); // 1st query int index = 0; int value = 2; updateValue(index, value, a, n); System.out.println(tree[0]); // 2nd query index = 3; value = 5; updateValue(index, value, a, n); System.out.println(tree[0]); } } // This code is contributed by vt_m.
Python3
# Python3 program to print the Leftover element # after performing alternate Bitwise OR and # Bitwise XOR operations to the pairs. N = 1000 # array to store the tree tree = [None] * N # array to store the level of every parent level = [None] * N # function to construct the tree def constructTree(low, high, pos, a): if low == high: # level of child is always 0 level[pos], tree[pos] = 0, a[high] return mid = (low + high) // 2 # Recursive call constructTree(low, mid, 2 * pos + 1, a) constructTree(mid + 1, high, 2 * pos + 2, a) # Increase the level of every parent, # which is level of child + 1 level[pos] = level[2 * pos + 1] + 1 # If the parent is at odd level, # then do a bitwise OR if level[pos] & 1: tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2] # If the parent is at even level, # then do a bitwise XOR else: tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2] # Function that updates the tree def update(low, high, pos, index, a): # If it is a leaf and the leaf # which is to be updated if low == high and low == index: tree[pos] = a[low] return # out of range if index < low or index > high: return # not a leaf then recurse if low != high: mid = (low + high) // 2 # recursive call update(low, mid, 2 * pos + 1, index, a) update(mid + 1, high, 2 * pos + 2, index, a) # check if the parent is at odd or even level # and perform OR or XOR according to that if level[pos] & 1: tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2] else: tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2] # Function that assigns value to a[index] # and calls update function to update the tree def updateValue(index, value, a, n): a[index] = value update(0, n - 1, 0, index, a) # Driver Code if __name__ == "__main__": a = [1, 4, 5, 6] n = len(a) # builds the tree constructTree(0, n - 1, 0, a) # 1st query index, value = 0, 2 updateValue(index, value, a, n) print(tree[0]) # 2nd query index, value = 3, 5 updateValue(index, value, a, n) print(tree[0]) # This code is contributed by Rituraj Jain
C#
// C# program to print the Leftover // element after performing alternate // Bitwise OR and Bitwise XOR // operations to the pairs. using System; public class GFG { static int N = 1000; // array to store the tree static int []tree = new int[N]; // array to store the level of // every parent static int []level = new int[N]; // function to construct the // tree static void constructTree(int low, int high, int pos, int []a) { if (low == high) { // level of child is always 0 level[pos] = 0; tree[pos] = a[high]; return; } int mid = (low + high) / 2; // recursive call constructTree(low, mid, 2 * pos + 1, a); constructTree(mid + 1, high, 2 * pos + 2, a); // increase the level of every parent, // which is level of child + 1 level[pos] = level[2 * pos + 1] + 1; // if the parent is at odd level, // then do a bitwise OR if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; // if the parent is at even level, // then do a bitwise XOR else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } // function that updates the tree static void update(int low, int high, int pos, int index, int []a) { // if it is a leaf and the leaf // which is to be updated if (low == high && low == index) { tree[pos] = a[low]; return; } // out of range if (index < low || index > high) return; // not a leaf then recurse if (low != high) { int mid = (low + high) / 2; // recursive call update(low, mid, 2 * pos + 1, index, a); update(mid + 1, high, 2 * pos + 2, index, a); // check if the parent is at odd // or even level and perform OR // or XOR according to that if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } } // function that assigns value to a[index] // and calls update function to update // the tree static void updateValue(int index, int value, int []a, int n) { a[index] = value; update(0, n - 1, 0, index, a); } // Driver Code static public void Main () { int []a = { 1, 4, 5, 6 }; int n = a.Length;; // builds the tree constructTree(0, n - 1, 0, a); // 1st query int index = 0; int value = 2; updateValue(index, value, a, n); Console.WriteLine(tree[0]); // 2nd query index = 3; value = 5; updateValue(index, value, a, n); Console.WriteLine(tree[0]); } } // This code is contributed by vt_m.
Javascript
<script> // Javascript program to print the Leftover // element after performing alternate // Bitwise OR and Bitwise XOR // operations to the pairs. let N = 1000; // array to store the tree let tree = new Array(N); tree.fill(0); // array to store the level of // every parent let level = new Array(N); level.fill(0); // function to construct the // tree function constructTree(low, high, pos, a) { if (low == high) { // level of child is always 0 level[pos] = 0; tree[pos] = a[high]; return; } let mid = parseInt((low + high) / 2, 10); // recursive call constructTree(low, mid, 2 * pos + 1, a); constructTree(mid + 1, high, 2 * pos + 2, a); // increase the level of every parent, // which is level of child + 1 level[pos] = level[2 * pos + 1] + 1; // if the parent is at odd level, // then do a bitwise OR if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; // if the parent is at even level, // then do a bitwise XOR else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } // function that updates the tree function update(low, high, pos, index, a) { // if it is a leaf and the leaf // which is to be updated if (low == high && low == index) { tree[pos] = a[low]; return; } // out of range if (index < low || index > high) return; // not a leaf then recurse if (low != high) { let mid = parseInt((low + high) / 2, 10); // recursive call update(low, mid, 2 * pos + 1, index, a); update(mid + 1, high, 2 * pos + 2, index, a); // check if the parent is at odd // or even level and perform OR // or XOR according to that if ((level[pos] & 1) > 0) tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2]; else tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2]; } } // function that assigns value to a[index] // and calls update function to update // the tree function updateValue(index, value, a, n) { a[index] = value; update(0, n - 1, 0, index, a); } let a = [ 1, 4, 5, 6 ]; let n = a.length;; // builds the tree constructTree(0, n - 1, 0, a); // 1st query let index = 0; let value = 2; updateValue(index, value, a, n); document.write(tree[0] + "</br>"); // 2nd query index = 3; value = 5; updateValue(index, value, a, n); document.write(tree[0]); </script>
Producción:
1 3
Complejidad del tiempo :
- Construcción del árbol: O(N)
- Consulta de respuesta: O (log 2 N)
Complejidad espacial : O(N)