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)