Dada una array N * N mat[][] que consta de enteros no negativos y algunas consultas que consisten en la esquina superior izquierda e inferior derecha de la subarray, la tarea es encontrar el AND bit a bit de todos los elementos de la subarray dada en cada consulta.
Ejemplos:
Entrada: mat[][] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}},
q[] = {{1, 1, 1, 1}, { 1, 2, 2, 2}}
Salida:
5
0
Consulta 1: El único elemento en la subarray es 5.
Consulta 2: 6 Y 9 = 0Entrada: mat[][] = {
{12, 23, 13},
{41, 15, 46},
{75, 82, 123}},
q[] = {{0, 0, 2, 2}, { 1, 1, 2, 2}}
Salida:
0
2
Enfoque ingenuo: iterar a través de la subarray y encontrar el AND bit a bit de todos los números en ese rango. Esto tomará O(n 2 ) tiempo para cada consulta en el peor de los casos.
Enfoque eficiente: si observamos los números enteros como un número binario, podemos ver fácilmente que la condición para que se establezca el i – ésimo bit de nuestra respuesta es que se debe establecer el i -ésimo bit de todos los enteros en la subarray.
Entonces, calcularemos el conteo de prefijos para cada bit. Usaremos esto para encontrar el número de enteros en la subarray con i -ésimo conjunto de bits. Si es igual al total de elementos de la subarray, también se establecerá el i -ésimo bit de nuestra respuesta.
Para esto, crearemos una array 3d, prefix_count[][][] donde prefix_count[i][x][y]almacenará el recuento de todos los elementos de la subarray con la esquina superior izquierda en {0, 0} y la esquina inferior derecha en {x, y} y el i -ésimo conjunto de bits. Consulte
este artículo para comprender prefix_count en caso de array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define bitscount 32
#define n 3
using namespace std;
// Array to store bit-wise
// prefix count
int prefix_count[bitscount][n][n];
// Function to find the prefix sum
void findPrefixCount(int arr[][n])
{
// Loop for each bit
for (int i = 0; i < bitscount; i++) {
// Loop to find prefix-count
// for each row
for (int j = 0; j < n; j++) {
prefix_count[i][j][0] = ((arr[j][0] >> i) & 1);
for (int k = 1; k < n; k++) {
prefix_count[i][j][k] = ((arr[j][k] >> i) & 1);
prefix_count[i][j][k] += prefix_count[i][j][k - 1];
}
}
}
// Finding column-wise prefix
// count
for (int i = 0; i < bitscount; i++)
for (int j = 1; j < n; j++)
for (int k = 0; k < n; k++)
prefix_count[i][j][k] += prefix_count[i][j - 1][k];
}
// Function to return the result for a query
int rangeAnd(int x1, int y1, int x2, int y2)
{
// To store the answer
int ans = 0;
// Loop for each bit
for (int i = 0; i < bitscount; i++) {
// To store the number of variables
// with ith bit set
int p;
if (x1 == 0 and y1 == 0)
p = prefix_count[i][x2][y2];
else if (x1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x2][y1 - 1];
else if (y1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x1 - 1][y2];
else
p = prefix_count[i][x2][y2]
- prefix_count[i][x1 - 1][y2]
- prefix_count[i][x2][y1 - 1]
+ prefix_count[i][x1 - 1][y1 - 1];
// If count of variables whose ith bit
// is set equals to the total
// elements in the sub-matrix
if (p == (x2 - x1 + 1) * (y2 - y1 + 1))
ans = (ans | (1 << i));
}
return ans;
}
// Driver code
int main()
{
int arr[][n] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
findPrefixCount(arr);
int queries[][4] = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } };
int q = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < q; i++)
cout << rangeAnd(queries[i][0],
queries[i][1],
queries[i][2],
queries[i][3])
<< endl;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int bitscount = 32 ;
final static int n = 3 ;
// Array to store bit-wise
// prefix count
static int prefix_count[][][] = new int [bitscount][n][n];
// Function to find the prefix sum
static void findPrefixCount(int arr[][])
{
// Loop for each bit
for (int i = 0; i < bitscount; i++)
{
// Loop to find prefix-count
// for each row
for (int j = 0; j < n; j++)
{
prefix_count[i][j][0] = ((arr[j][0] >> i) & 1);
for (int k = 1; k < n; k++)
{
prefix_count[i][j][k] = ((arr[j][k] >> i) & 1);
prefix_count[i][j][k] += prefix_count[i][j][k - 1];
}
}
}
// Finding column-wise prefix
// count
for (int i = 0; i < bitscount; i++)
for (int j = 1; j < n; j++)
for (int k = 0; k < n; k++)
prefix_count[i][j][k] += prefix_count[i][j - 1][k];
}
// Function to return the result for a query
static int rangeAnd(int x1, int y1, int x2, int y2)
{
// To store the answer
int ans = 0;
// Loop for each bit
for (int i = 0; i < bitscount; i++)
{
// To store the number of variables
// with ith bit set
int p;
if (x1 == 0 && y1 == 0)
p = prefix_count[i][x2][y2];
else if (x1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x2][y1 - 1];
else if (y1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x1 - 1][y2];
else
p = prefix_count[i][x2][y2]
- prefix_count[i][x1 - 1][y2]
- prefix_count[i][x2][y1 - 1]
+ prefix_count[i][x1 - 1][y1 - 1];
// If count of variables whose ith bit
// is set equals to the total
// elements in the sub-matrix
if (p == (x2 - x1 + 1) * (y2 - y1 + 1))
ans = (ans | (1 << i));
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int arr[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
findPrefixCount(arr);
int queries[][] = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } };
int q = queries.length;
for (int i = 0; i < q; i++)
System.out.println( rangeAnd(queries[i][0],
queries[i][1],
queries[i][2],
queries[i][3]) );
}
}
// This code is contributed by AnkitRai
Python3
# Python 3 implementation of the approach bitscount = 32 n = 3 # Array to store bit-wise # prefix count prefix_count = [[[0 for i in range(n)] for j in range(n)] for k in range(bitscount)] # Function to find the prefix sum def findPrefixCount(arr): # Loop for each bit for i in range(bitscount): # Loop to find prefix-count # for each row for j in range(n): prefix_count[i][j][0] = ((arr[j][0] >> i) & 1) for k in range(1,n): prefix_count[i][j][k] = ((arr[j][k] >> i) & 1) prefix_count[i][j][k] += prefix_count[i][j][k - 1] # Finding column-wise prefix # count for i in range(bitscount): for j in range(1,n): for k in range(n): prefix_count[i][j][k] += prefix_count[i][j - 1][k] # Function to return the result for a query def rangeOr(x1, y1, x2, y2): # To store the answer ans = 0 # Loop for each bit for i in range(bitscount): # To store the number of variables # with ith bit set if (x1 == 0 and y1 == 0): p = prefix_count[i][x2][y2] elif (x1 == 0): p = prefix_count[i][x2][y2] - prefix_count[i][x2][y1 - 1] elif (y1 == 0): p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] else: p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] - prefix_count[i][x2][y1 - 1] + prefix_count[i][x1 - 1][y1 - 1]; # If count of variables with ith bit # set is greater than 0 if (p == (x2 - x1 + 1) * (y2 - y1 + 1)): ans = (ans | (1 << i)) return ans # Driver code if __name__ == '__main__': arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] findPrefixCount(arr) queries = [[1, 1, 1, 1], [1, 2, 2, 2]] q = len(queries) for i in range(q): print(rangeOr(queries[i][0],queries[i][1],queries[i][2],queries[i][3])) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int bitscount = 32 ;
static int n = 3 ;
// Array to store bit-wise
// prefix count
static int [,,]prefix_count = new int [bitscount,n,n];
// Function to find the prefix sum
static void findPrefixCount(int [,]arr)
{
// Loop for each bit
for (int i = 0; i < bitscount; i++)
{
// Loop to find prefix-count
// for each row
for (int j = 0; j < n; j++)
{
prefix_count[i,j,0] = ((arr[j,0] >> i) & 1);
for (int k = 1; k < n; k++)
{
prefix_count[i, j, k] = ((arr[j,k] >> i) & 1);
prefix_count[i, j, k] += prefix_count[i, j, k - 1];
}
}
}
// Finding column-wise prefix
// count
for (int i = 0; i < bitscount; i++)
for (int j = 1; j < n; j++)
for (int k = 0; k < n; k++)
prefix_count[i, j, k] += prefix_count[i, j - 1, k];
}
// Function to return the result for a query
static int rangeAnd(int x1, int y1, int x2, int y2)
{
// To store the answer
int ans = 0;
// Loop for each bit
for (int i = 0; i < bitscount; i++)
{
// To store the number of variables
// with ith bit set
int p;
if (x1 == 0 && y1 == 0)
p = prefix_count[i, x2, y2];
else if (x1 == 0)
p = prefix_count[i, x2, y2]
- prefix_count[i, x2, y1 - 1];
else if (y1 == 0)
p = prefix_count[i, x2, y2]
- prefix_count[i, x1 - 1, y2];
else
p = prefix_count[i, x2, y2]
- prefix_count[i, x1 - 1, y2]
- prefix_count[i, x2, y1 - 1]
+ prefix_count[i, x1 - 1, y1 - 1];
// If count of variables whose ith bit
// is set equals to the total
// elements in the sub-matrix
if (p == (x2 - x1 + 1) * (y2 - y1 + 1))
ans = (ans | (1 << i));
}
return ans;
}
// Driver code
public static void Main (String[] args)
{
int [,]arr = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
findPrefixCount(arr);
int [,]queries = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } };
int q = queries.GetLength(0);
for (int i = 0; i < q; i++)
Console.WriteLine( rangeAnd(queries[i,0],
queries[i,1],
queries[i,2],
queries[i,3]) );
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
let bitscount = 32;
let n = 3 ;
// Array to store bit-wise
// prefix count
let prefix_count = new Array(bitscount);
for(let i = 0; i < bitscount; i++)
{
prefix_count[i] = new Array(n);
for(let j = 0; j < n; j++)
{
prefix_count[i][j] = new Array(n);
for(let k = 0; k < n; k++)
{
prefix_count[i][j][k] = 0;
}
}
}
// Function to find the prefix sum
function findPrefixCount(arr)
{
// Loop for each bit
for(let i = 0; i < bitscount; i++)
{
// Loop to find prefix-count
// for each row
for(let j = 0; j < n; j++)
{
prefix_count[i][j][0] = ((arr[j][0] >> i) & 1);
for(let k = 1; k < n; k++)
{
prefix_count[i][j][k] = (
(arr[j][k] >> i) & 1);
prefix_count[i][j][k] +=
prefix_count[i][j][k - 1];
}
}
}
// Finding column-wise prefix
// count
for(let i = 0; i < bitscount; i++)
for(let j = 1; j < n; j++)
for(let k = 0; k < n; k++)
prefix_count[i][j][k] +=
prefix_count[i][j - 1][k];
}
// Function to return the result for a query
function rangeAnd(x1, y1, x2, y2)
{
// To store the answer
let ans = 0;
// Loop for each bit
for(let i = 0; i < bitscount; i++)
{
// To store the number of variables
// with ith bit set
let p;
if (x1 == 0 && y1 == 0)
p = prefix_count[i][x2][y2];
else if (x1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x2][y1 - 1];
else if (y1 == 0)
p = prefix_count[i][x2][y2]
- prefix_count[i][x1 - 1][y2];
else
p = prefix_count[i][x2][y2] -
prefix_count[i][x1 - 1][y2] -
prefix_count[i][x2][y1 - 1] +
prefix_count[i][x1 - 1][y1 - 1];
// If count of variables whose ith bit
// is set equals to the total
// elements in the sub-matrix
if (p == (x2 - x1 + 1) * (y2 - y1 + 1))
ans = (ans | (1 << i));
}
return ans;
}
// Driver code
let arr = [ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ];
findPrefixCount(arr);
let queries = [ [ 1, 1, 1, 1 ],
[ 1, 2, 2, 2 ] ];
let q = queries.length;
for(let i = 0; i < q; i++)
document.write(rangeAnd(queries[i][0],
queries[i][1],
queries[i][2],
queries[i][3]) + "</br>");
// This code is contributed by divyeshrabadiya07
</script>
Producción:
5 0
La complejidad del tiempo para el cálculo previo es O(n 2 ) y cada consulta se puede responder en O(1)
Espacio Auxiliar: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA