Consultas para AND bit a bit en la array dada

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: 


Consulta 1: El único elemento en la subarray es 5. 
Consulta 2: 6 Y 9 = 0

Entrada: mat[][] = { 
{12, 23, 13}, 
{41, 15, 46}, 
{75, 82, 123}}, 
q[] = {{0, 0, 2, 2}, { 1, 1, 2, 2}} 
Salida: 


 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *