Recuento de celdas en Binary Matrix que tienen el mismo XOR bit a bit de esa fila y columna

Dada una array binaria arr[][] de N filas y M columnas. La tarea es encontrar el número de celdas en la array, donde Bitwise XOR de todos los elementos en su fila y columna son iguales.

Ejemplos:

Entrada: N = 2, M = 2, arr[][] = [[0, 0], [1, 0]] 
Salida: 2
Explicación: Hay un total de 4 celdas. 
De las cuales solo 2 celdas cumplen la condición anterior.
Celda {0, 1} y {1, 0} (la indexación se basa en 0).

Entrada: N = 2, M = 2, arr[][] = [[1, 0], [0, 1]]
Salida: 4
Explicación: Hay un total de 4 celdas. 
De las cuales las 4 celdas cumplen la condición. 
Si tomamos cualquiera de las celdas, entonces el xor de todos los elementos 
en su fila y columna es igual a 1 .

Enfoque: la idea para resolver el problema utilizando el prefijo Xor array y el enfoque codicioso es la siguiente:

Calcule previamente el valor xor de todos los elementos en cada fila y columna. 
Luego, para cada celda (celda (i, j) ) verifique si el valor xor de todos los elementos de esa fila i y esa columna j es igual o no.

Siga los pasos a continuación para resolver este problema:

• En primer lugar, calcule previamente el xor de todos los elementos de cada fila y columna por separado.
• Itere a través de cada celda de la array, deje que la celda actual sea (i, j) donde i es el índice de fila y j es el índice de columna.
  • Si el xor de todos los elementos de la fila i y la columna j es igual, aumente la cuenta uno.
• Devuelve la cuenta .

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of cells
int countCells(vector<vector<int> >& v)
{
    // n = number of rows and
    // m = number of columns
    int n = v.size(), m = v[0].size();
 
    vector<int> row(n), col(m);
 
    // Pre-compute the xor of all the
    // elements of each row.
    for (int i = 0; i < n; i++) {
        int val = 0;
        for (int j = 0; j < m; j++) {
            val ^= v[i][j];
        }
        row[i] = val;
    }
 
    // Try to pre-compute the xor of all
    // the elements of each column.
    for (int j = 0; j < m; j++) {
        int val = 0;
        for (int i = 0; i < n; i++) {
            val ^= v[i][j];
        }
        col[j] = val;
    }
 
    // Here 'ans' will store the number of
    // cells that satisfy the condition
    // of the problem.
    int ans = 0;
 
    // Loop to find the
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            // If the xor value of all the
            // elements of 'ith' row and
            // 'jth' column is same then it
            // is a cell which satisfy
            // the condition.
            if (row[i] == col[j]) {
                ans++;
            }
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > arr
        = { { 1, 0 }, { 0, 1 } };
 
    // Function call
    cout << countCells(arr);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
  // Function to find the count of cells
  static int countCells(int[][] v)
  {
    // n = number of rows and
    // m = number of columns
    int n = v.length, m = v[0].length;
 
    int[] row = new int[n];
    int[] col = new int[m];
 
    // Pre-compute the xor of all the
    // elements of each row.
    for (int i = 0; i < n; i++) {
      int val = 0;
      for (int j = 0; j < m; j++) {
        val ^= v[i][j];
      }
      row[i] = val;
    }
 
    // Try to pre-compute the xor of all
    // the elements of each column.
    for (int j = 0; j < m; j++) {
      int val = 0;
      for (int i = 0; i < n; i++) {
        val ^= v[i][j];
      }
      col[j] = val;
    }
 
    // Here 'ans' will store the number of
    // cells that satisfy the condition
    // of the problem.
    int ans = 0;
 
    // Loop to find the
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
 
        // If the xor value of all the
        // elements of 'ith' row and
        // 'jth' column is same then it
        // is a cell which satisfy
        // the condition.
        if (row[i] == col[j]) {
          ans++;
        }
      }
    }
 
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[][] arr
      = { { 1, 0 }, { 0, 1 } };
 
    // Function call
    System.out.println(countCells(arr));
  }
}
 
// This code is contributed by sanjoy_62.

# Python3 code to implement the approach
 
# Function to find the count of cells
def countCells(v):
 
    # n = number of rows and
    # m = number of columns
    n, m = len(v), len(v[0])
 
    row, col = [0 for _ in range(n)], [0 for _ in range(m)]
 
    # Pre-compute the xor of all the
    # elements of each row.
    for i in range(0, n):
        val = 0
        for j in range(0, m):
            val ^= v[i][j]
 
        row[i] = val
 
    # Try to pre-compute the xor of all
    # the elements of each column.
    for j in range(0, m):
        val = 0
        for i in range(0, n):
            val ^= v[i][j]
 
        col[j] = val
 
    # Here 'ans' will store the number of
    # cells that satisfy the condition
    # of the problem.
    ans = 0
 
    # Loop to find the
    for i in range(0, n):
        for j in range(0, m):
 
            # If the xor value of all the
            # elements of 'ith' row and
            # 'jth' column is same then it
            # is a cell which satisfy
            # the condition.
            if (row[i] == col[j]):
                ans += 1
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [[1, 0], [0, 1]]
 
    # Function call
    print(countCells(arr))
 
# This code is contributed by rakeshsahni

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
  // Function to find the count of cells
  static int countCells(int[,] v)
  {
    // n = number of rows and
    // m = number of columns
    int n = v.GetLength(0);
    int m = 2;
 
    int[] row = new int[n];
    int[] col = new int[m];
 
    // Pre-compute the xor of all the
    // elements of each row.
    for (int i = 0; i < n; i++) {
      int val = 0;
      for (int j = 0; j < m; j++) {
        val ^= v[i, j];
      }
      row[i] = val;
    }
 
    // Try to pre-compute the xor of all
    // the elements of each column.
    for (int j = 0; j < m; j++) {
      int val = 0;
      for (int i = 0; i < n; i++) {
        val ^= v[i, j];
      }
      col[j] = val;
    }
 
    // Here 'ans' will store the number of
    // cells that satisfy the condition
    // of the problem.
    int ans = 0;
 
    // Loop to find the
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
 
        // If the xor value of all the
        // elements of 'ith' row and
        // 'jth' column is same then it
        // is a cell which satisfy
        // the condition.
        if (row[i] == col[j]) {
          ans++;
        }
      }
    }
 
    return ans;
  }
 
// Driver Code
public static void Main()
{
    int[,] arr
      = { { 1, 0 }, { 0, 1 } };
 
    // Function call
    Console.Write(countCells(arr));
}
}
 
// This code is contributed by code_hunt.

<script>
 
// JavaScript code to implement the approach
 
// Function to find the count of cells
function countCells(v){
 
    // n = number of rows and
    // m = number of columns
    let n = v.length,m = v[0].length
 
    let row = new Array(n).fill(0), col = new Array(m).fill(0)
 
    // Pre-compute the xor of all the
    // elements of each row.
    for(let i = 0; i < n; i++)
    {
        let val = 0
        for(let j = 0; j < m; j++)
        {
            val ^= v[i][j]
        }
 
        row[i] = val
    }
    // Try to pre-compute the xor of all
    // the elements of each column.
    for(let j = 0; j < m; j++)
    {
        let val = 0
        for(let i = 0; i < n; i++)
        {
            val ^= v[i][j]
        }
        col[j] = val
    }
 
    // Here 'ans' will store the number of
    // cells that satisfy the condition
    // of the problem.
    ans = 0
 
    // Loop to find the
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < m; j++)
        {
 
            // If the xor value of all the
            // elements of 'ith' row and
            // 'jth' column is same then it
            // is a cell which satisfy
            // the condition.
            if (row[i] == col[j])
                ans += 1
        }
    }
    return ans
}
 
// Driver Code
let arr = [[1, 0], [0, 1]]
 
// Function call
document.write(countCells(arr),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

4

Complejidad de tiempo : O (N * M), ya que estamos usando bucles anidados para atravesar N * M veces.

Espacio auxiliar: O (N + M), ya que estamos usando espacio adicional para filas y columnas de arrays.