Dada una array arr[] que consta de N enteros positivos y una array 2D Q[][] que consta de consultas del tipo {i, val} , la tarea de cada consulta es reemplazar arr[i] por val y calcular el Bitwise Y de la array modificada.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, Q[][] = {{0, 2}, {3, 3}, {4, 2}}
Salida: 0 0 2
Explicación:
Consulta 1: actualice A[0] a 2, luego la array se modifica a {2, 2, 3, 4, 5}. El AND bit a bit de todos los elementos es 0.
Consulta 2: actualice A[3] a 3, luego la array se modifica a {2, 2, 3, 3, 5}. El AND bit a bit de todos los elementos es 0.
Consulta 3: actualice A[4] a 2, luego la array modificada, A[]={2, 2, 3, 3, 2}. El AND bit a bit de todos los elementos es 2.Entrada: arr[] = {1, 2, 3}, Q[][] = {{1, 5}, {2, 4}}
Salida: 1 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es actualizar el elemento de la array para cada consulta y luego encontrar el AND bit a bit de todos los elementos de la array recorriendo la array en cada consulta.
Complejidad temporal: O(N * Q)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de una array auxiliar, digamos bitCount[][] de tamaño 32 * N para almacenar la suma de los bits establecidos en la posición i hasta el j -ésimo índice de la array. Entonces, bitCount[i][N – 1] representa la suma total de bits establecidos en la posición i usando todos los elementos de la array. Siga los pasos a continuación para resolver el problema:
- Inicialice una array bitCount[32][N] para almacenar los bits establecidos de los elementos de la array.
- Iterar sobre el rango [0, 31] usando la variable i y realizar los siguientes pasos:
- Si el valor de A[0] se establece en la i -ésima posición, actualice bitCount[i][0] a 1 . De lo contrario, actualícelo a 0 .
- Recorra la array A[] en el rango [1, N – 1] usando la variable j y realice los siguientes pasos:
- Si el valor de A[j] se establece en la i -ésima posición, actualice bitCount[i][j] a 1 .
- Agregue el valor de bitCount[i][j – 1] a bitCount[i][j] .
- Recorra la array dada de consultas Q[][] y realice los siguientes pasos:
- Inicialice una variable, digamos res como 0 , para almacenar el resultado de la consulta actual.
- Almacene el valor actual en el índice dado en currentVal y el nuevo valor en newVal .
- Iterar sobre el rango [0, 31] usando la variable i
- Si newVal se establece en el índice i y currentVal no se establece, entonces incremente el prefijo[i][N – 1] en 1 .
- De lo contrario, si currentVal se establece en el índice i y newVal no se establece, entonces disminuya el prefijo[i][N – 1] en 1 .
- Si el valor del prefijo[i][N – 1] es igual a N , establezca este bit en res .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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;
// Store the number of set bits at
// each position
int prefixCount[32][10000];
// Function to precompute the prefix
// count array
void findPrefixCount(vector<int> arr,
int size)
{
// Iterate over the range[0, 31]
for (int i = 0; i < 32; i++) {
// Set the bit at position i
// if arr[0] is set at position i
prefixCount[i][0]
= ((arr[0] >> i) & 1);
// Traverse the array and
// take prefix sum
for (int j = 1; j < size; j++) {
// Update prefixCount[i][j]
prefixCount[i][j]
= ((arr[j] >> i) & 1);
prefixCount[i][j]
+= prefixCount[i][j - 1];
}
}
}
// Function to find the Bitwise AND
// of all array elements
void arrayBitwiseAND(int size)
{
// Stores the required result
int result = 0;
// Iterate over the range [0, 31]
for (int i = 0; i < 32; i++) {
// Stores the number of set
// bits at position i
int temp = prefixCount[i]
[size - 1];
// If temp is N, then set ith
// position in the result
if (temp == size)
result = (result | (1 << i));
}
// Print the result
cout << result << " ";
}
// Function to update the prefix count
// array in each query
void applyQuery(int currentVal, int newVal,
int size)
{
// Iterate through all the bits
// of the current number
for (int i = 0; i < 32; i++) {
// Store the bit at position
// i in the current value and
// the new value
int bit1 = ((currentVal >> i) & 1);
int bit2 = ((newVal >> i) & 1);
// If bit2 is set and bit1 is
// unset, then increase the
// set bits at position i by 1
if (bit2 > 0 && bit1 == 0)
prefixCount[i][size - 1]++;
// If bit1 is set and bit2 is
// unset, then decrease the
// set bits at position i by 1
else if (bit1 > 0 && bit2 == 0)
prefixCount[i][size - 1]--;
}
}
// Function to find the bitwise AND
// of the array after each query
void findbitwiseAND(
vector<vector<int> > queries,
vector<int> arr, int N, int M)
{
// Fill the prefix count array
findPrefixCount(arr, N);
// Traverse the queries
for (int i = 0; i < M; i++) {
// Store the index and
// the new value
int id = queries[i][0];
int newVal = queries[i][1];
// Store the current element
// at the index
int currentVal = arr[id];
// Update the array element
arr[id] = newVal;
// Apply the changes to the
// prefix count array
applyQuery(currentVal, newVal, N);
// Print the bitwise AND of
// the modified array
arrayBitwiseAND(N);
}
}
// Driver Code
int main()
{
vector<int> arr{ 1, 2, 3, 4, 5 };
vector<vector<int> > queries{ { 0, 2 },
{ 3, 3 },
{ 4, 2 } };
int N = arr.size();
int M = queries.size();
findbitwiseAND(queries, arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Store the number of set bits at
// each position
static int prefixCount[][];
// Function to precompute the prefix
// count array
static void findPrefixCount(int arr[], int size)
{
// Iterate over the range[0, 31]
for(int i = 0; i < 32; i++)
{
// Set the bit at position i
// if arr[0] is set at position i
prefixCount[i][0] = ((arr[0] >> i) & 1);
// Traverse the array and
// take prefix sum
for(int j = 1; j < size; j++)
{
// Update prefixCount[i][j]
prefixCount[i][j] = ((arr[j] >> i) & 1);
prefixCount[i][j] += prefixCount[i][j - 1];
}
}
}
// Function to find the Bitwise AND
// of all array elements
static void arrayBitwiseAND(int size)
{
// Stores the required result
int result = 0;
// Iterate over the range [0, 31]
for(int i = 0; i < 32; i++)
{
// Stores the number of set
// bits at position i
int temp = prefixCount[i][size - 1];
// If temp is N, then set ith
// position in the result
if (temp == size)
result = (result | (1 << i));
}
// Print the result
System.out.print(result + " ");
}
// Function to update the prefix count
// array in each query
static void applyQuery(int currentVal, int newVal,
int size)
{
// Iterate through all the bits
// of the current number
for(int i = 0; i < 32; i++)
{
// Store the bit at position
// i in the current value and
// the new value
int bit1 = ((currentVal >> i) & 1);
int bit2 = ((newVal >> i) & 1);
// If bit2 is set and bit1 is
// unset, then increase the
// set bits at position i by 1
if (bit2 > 0 && bit1 == 0)
prefixCount[i][size - 1]++;
// If bit1 is set and bit2 is
// unset, then decrease the
// set bits at position i by 1
else if (bit1 > 0 && bit2 == 0)
prefixCount[i][size - 1]--;
}
}
// Function to find the bitwise AND
// of the array after each query
static void findbitwiseAND(int queries[][], int arr[],
int N, int M)
{
prefixCount = new int[32][10000];
// Fill the prefix count array
findPrefixCount(arr, N);
// Traverse the queries
for(int i = 0; i < M; i++)
{
// Store the index and
// the new value
int id = queries[i][0];
int newVal = queries[i][1];
// Store the current element
// at the index
int currentVal = arr[id];
// Update the array element
arr[id] = newVal;
// Apply the changes to the
// prefix count array
applyQuery(currentVal, newVal, N);
// Print the bitwise AND of
// the modified array
arrayBitwiseAND(N);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int queries[][] = { { 0, 2 }, { 3, 3 },
{ 4, 2 } };
int N = arr.length;
int M = queries.length;
findbitwiseAND(queries, arr, N, M);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Store the number of set bits at # each position prefixCount = [[0 for x in range(32)] for y in range(10000)] # Function to precompute the prefix # count array def findPrefixCount(arr, size): # Iterate over the range[0, 31] for i in range(32): # Set the bit at position i # if arr[0] is set at position i prefixCount[i][0] = ((arr[0] >> i) & 1) # Traverse the array and # take prefix sum for j in range(1, size): # Update prefixCount[i][j] prefixCount[i][j] = ((arr[j] >> i) & 1) prefixCount[i][j] += prefixCount[i][j - 1] # Function to find the Bitwise AND # of all array elements def arrayBitwiseAND(size): # Stores the required result result = 0 # Iterate over the range [0, 31] for i in range(32): # Stores the number of set # bits at position i temp = prefixCount[i][size - 1] # If temp is N, then set ith # position in the result if (temp == size): result = (result | (1 << i)) # Print the result print(result, end = " ") # Function to update the prefix count # array in each query def applyQuery(currentVal, newVal, size): # Iterate through all the bits # of the current number for i in range(32): # Store the bit at position # i in the current value and # the new value bit1 = ((currentVal >> i) & 1) bit2 = ((newVal >> i) & 1) # If bit2 is set and bit1 is # unset, then increase the # set bits at position i by 1 if (bit2 > 0 and bit1 == 0): prefixCount[i][size - 1] += 1 # If bit1 is set and bit2 is # unset, then decrease the # set bits at position i by 1 elif (bit1 > 0 and bit2 == 0): prefixCount[i][size - 1] -= 1 # Function to find the bitwise AND # of the array after each query def findbitwiseAND(queries, arr, N, M): # Fill the prefix count array findPrefixCount(arr, N) # Traverse the queries for i in range(M): # Store the index and # the new value id = queries[i][0] newVal = queries[i][1] # Store the current element # at the index currentVal = arr[id] # Update the array element arr[id] = newVal # Apply the changes to the # prefix count array applyQuery(currentVal, newVal, N) # Print the bitwise AND of # the modified array arrayBitwiseAND(N) # Driver Code if __name__ == "__main__": arr = [ 1, 2, 3, 4, 5 ] queries = [ [ 0, 2 ], [ 3, 3 ], [ 4, 2 ] ] N = len(arr) M = len(queries) findbitwiseAND(queries, arr, N, M) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Store the number of set bits at
// each position
static int [,]prefixCount = new int[32, 10000];
// Function to precompute the prefix
// count array
static void findPrefixCount(List<int> arr,
int size)
{
// Iterate over the range[0, 31]
for(int i = 0; i < 32; i++)
{
// Set the bit at position i
// if arr[0] is set at position i
prefixCount[i, 0] = ((arr[0] >> i) & 1);
// Traverse the array and
// take prefix sum
for(int j = 1; j < size; j++)
{
// Update prefixCount[i][j]
prefixCount[i, j] = ((arr[j] >> i) & 1);
prefixCount[i, j] += prefixCount[i, j - 1];
}
}
}
// Function to find the Bitwise AND
// of all array elements
static void arrayBitwiseAND(int size)
{
// Stores the required result
int result = 0;
// Iterate over the range [0, 31]
for(int i = 0; i < 32; i++)
{
// Stores the number of set
// bits at position i
int temp = prefixCount[i, size - 1];
// If temp is N, then set ith
// position in the result
if (temp == size)
result = (result | (1 << i));
}
// Print the result
Console.Write(result + " ");
}
// Function to update the prefix count
// array in each query
static void applyQuery(int currentVal, int newVal,
int size)
{
// Iterate through all the bits
// of the current number
for(int i = 0; i < 32; i++)
{
// Store the bit at position
// i in the current value and
// the new value
int bit1 = ((currentVal >> i) & 1);
int bit2 = ((newVal >> i) & 1);
// If bit2 is set and bit1 is
// unset, then increase the
// set bits at position i by 1
if (bit2 > 0 && bit1 == 0)
prefixCount[i, size - 1]++;
// If bit1 is set and bit2 is
// unset, then decrease the
// set bits at position i by 1
else if (bit1 > 0 && bit2 == 0)
prefixCount[i, size - 1]--;
}
}
// Function to find the bitwise AND
// of the array after each query
static void findbitwiseAND(int [,]queries,
List<int> arr, int N, int M)
{
// Fill the prefix count array
findPrefixCount(arr, N);
// Traverse the queries
for(int i = 0; i < M; i++)
{
// Store the index and
// the new value
int id = queries[i,0];
int newVal = queries[i,1];
// Store the current element
// at the index
int currentVal = arr[id];
// Update the array element
arr[id] = newVal;
// Apply the changes to the
// prefix count array
applyQuery(currentVal, newVal, N);
// Print the bitwise AND of
// the modified array
arrayBitwiseAND(N);
}
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){ 1, 2, 3, 4, 5 };
int [,] queries = new int [3, 2]{ { 0, 2 },
{ 3, 3 },
{ 4, 2 } };
int N = arr.Count;
int M = 3;
findbitwiseAND(queries, arr, N, M);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// JavaScript program to implement
// the above approach
// Store the number of set bits at
// each position
let prefixCount = [[]];
// Function to precompute the prefix
// count array
function findPrefixCount(arr, size)
{
// Iterate over the range[0, 31]
for(let i = 0; i < 32; i++)
{
// Set the bit at position i
// if arr[0] is set at position i
prefixCount[i][0] = ((arr[0] >> i) & 1);
// Traverse the array and
// take prefix sum
for(let j = 1; j < size; j++)
{
// Update prefixCount[i][j]
prefixCount[i][j] = ((arr[j] >> i) & 1);
prefixCount[i][j] += prefixCount[i][j - 1];
}
}
}
// Function to find the Bitwise AND
// of all array elements
function arrayBitwiseAND(size)
{
// Stores the required result
let result = 0;
// Iterate over the range [0, 31]
for(let i = 0; i < 32; i++)
{
// Stores the number of set
// bits at position i
let temp = prefixCount[i][size - 1];
// If temp is N, then set ith
// position in the result
if (temp == size)
result = (result | (1 << i));
}
// Print the result
document.write(result + " ");
}
// Function to update the prefix count
// array in each query
function applyQuery(currentVal, newVal,
size)
{
// Iterate through all the bits
// of the current number
for(let i = 0; i < 32; i++)
{
// Store the bit at position
// i in the current value and
// the new value
let bit1 = ((currentVal >> i) & 1);
let bit2 = ((newVal >> i) & 1);
// If bit2 is set and bit1 is
// unset, then increase the
// set bits at position i by 1
if (bit2 > 0 && bit1 == 0)
prefixCount[i][size - 1]++;
// If bit1 is set and bit2 is
// unset, then decrease the
// set bits at position i by 1
else if (bit1 > 0 && bit2 == 0)
prefixCount[i][size - 1]--;
}
}
// Function to find the bitwise AND
// of the array after each query
function findbitwiseAND(queries, arr,
N, M)
{
prefixCount = new Array(32);
// Loop to create 2D array using 1D array
for (var i = 0; i < prefixCount.length; i++) {
prefixCount[i] = new Array(2);
}
// Fill the prefix count array
findPrefixCount(arr, N);
// Traverse the queries
for(let i = 0; i < M; i++)
{
// Store the index and
// the new value
let id = queries[i][0];
let newVal = queries[i][1];
// Store the current element
// at the index
let currentVal = arr[id];
// Update the array element
arr[id] = newVal;
// Apply the changes to the
// prefix count array
applyQuery(currentVal, newVal, N);
// Print the bitwise AND of
// the modified array
arrayBitwiseAND(N);
}
}
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let queries = [[ 0, 2 ], [ 3, 3 ],
[ 4, 2 ]];
let N = arr.length;
let M = queries.length;
findbitwiseAND(queries, arr, N, M);
// This code is contributed by code_hunt.
</script>
Producción:
0 0 2
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aimformohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA