Cuente los 1 en una array binaria con los índices restantes de su fila y columna llenos de 0

Dada una array binaria, mat[][] de tamaño M * N , la tarea es contar el número de 1 s de la array binaria dada cuya fila y columna correspondiente consta de 0 s solo en los índices restantes.

Ejemplos: 

Entrada: mat[][] = {{1, 0, 0}, {0, 0, 1}, {0, 0, 0}} 
Salida: 2 
Explicación: 
Las únicas dos celdas que cumplen las condiciones son (0, 0 ) y (1, 2). 
Por lo tanto, la cuenta es 2. 

Entrada: mat[][] = {{1, 0}, {1, 1}} 
Salida: 0 

Enfoque ingenuo: el enfoque más simple es iterar sobre la array y verificar la condición dada para todos los 1 presentes en la array dada atravesando su fila y columna correspondientes. Aumente el conteo de todos los 1 que cumplan la condición. Finalmente, imprima el conteo como la respuesta requerida.

Complejidad de Tiempo: O(M*N ² ) 
Espacio Auxiliar: O(M + N)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la idea de que la suma de dichas filas y columnas será solo 1 . Siga los pasos a continuación para resolver el problema: 

1. Inicialice dos arrays, rows[] y cols[] , para almacenar la suma de cada fila y cada columna de la array respectivamente.
2. Inicialice una variable, digamos cnt , para almacenar la cuenta de 1 s que satisface la condición dada.
3. Recorra la array para cada mat[i][j] = 1 , verifique si rows[i] y cols[j] son ​​1. Si se encuentra que es cierto, entonces incremente cnt .
4. Después de completar los pasos anteriores, imprima el valor final de count .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count required 1s
// from the given matrix
int numSpecial(vector<vector<int> >& mat)
{
 
    // Stores the dimensions of the mat[][]
    int m = mat.size(), n = mat[0].size();
 
    int rows[m];
    int cols[n];
 
    int i, j;
 
    // Calculate sum of rows
    for (i = 0; i < m; i++) {
        rows[i] = 0;
        for (j = 0; j < n; j++)
            rows[i] += mat[i][j];
    }
 
    // Calculate sum of columns
    for (i = 0; i < n; i++) {
 
        cols[i] = 0;
        for (j = 0; j < m; j++)
            cols[i] += mat[j][i];
    }
 
    // Stores required count of 1s
    int cnt = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
 
            // If current cell is 1
            // and sum of row and column is 1
            if (mat[i][j] == 1 && rows[i] == 1
                && cols[j] == 1)
 
                // Increment count of 1s
                cnt++;
        }
    }
 
    // Return the final count
    return cnt;
}
 
// Driver Code
int main()
{
    // Given matrix
    vector<vector<int> > mat
        = { { 1, 0, 0 }, { 0, 0, 1 }, { 0, 0, 0 } };
 
    // Function Call
    cout << numSpecial(mat) << endl;
 
    return 0;
}

// Java program for the above approach
class GFG{
     
// Function to count required 1s
// from the given matrix
static int numSpecial(int [][]mat)
{
     
    // Stores the dimensions of the mat[][]
    int m = mat.length;
    int n = mat[0].length;
  
    int []rows = new int[m];
    int []cols = new int[n];
  
    int i, j;
  
    // Calculate sum of rows
    for(i = 0; i < m; i++)
    {
        rows[i] = 0;
         
        for(j = 0; j < n; j++)
            rows[i] += mat[i][j];
    }
  
    // Calculate sum of columns
    for(i = 0; i < n; i++)
    {
        cols[i] = 0;
         
        for(j = 0; j < m; j++)
            cols[i] += mat[j][i];
    }
  
    // Stores required count of 1s
    int cnt = 0;
     
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
             
            // If current cell is 1
            // and sum of row and column is 1
            if (mat[i][j] == 1 &&
                  rows[i] == 1 &&
                  cols[j] == 1)
  
                // Increment count of 1s
                cnt++;
        }
    }
     
    // Return the final count
    return cnt;
}
  
// Driver Code
public static void main(String[] args)
{
     
    // Given matrix
    int [][]mat = { { 1, 0, 0 },
                    { 0, 0, 1 },
                    { 0, 0, 0 } };
  
    // Function call
    System.out.print(numSpecial(mat) + "\n");
}
}
  
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count required 1s
# from the given matrix
def numSpecial(mat):
     
    # Stores the dimensions
    # of the mat
    m = len(mat)
    n = len(mat[0])
 
    rows = [0] * m
    cols = [0] * n
 
    i, j = 0, 0
 
    # Calculate sum of rows
    for i in range(m):
        rows[i] = 0
 
        for j in range(n):
            rows[i] += mat[i][j]
 
    # Calculate sum of columns
    for i in range(n):
        cols[i] = 0
 
        for j in range(m):
            cols[i] += mat[j][i]
 
    # Stores required count of 1s
    cnt = 0
 
    for i in range(m):
        for j in range(n):
 
            # If current cell is 1
            # and sum of row and column is 1
            if (mat[i][j] == 1 and
                  rows[i] == 1 and
                  cols[j] == 1):
 
                # Increment count of 1s
                cnt += 1
 
    # Return the final count
    return cnt
 
# Driver Code
if __name__ == '__main__':
     
    # Given matrix
    mat = [ [ 1, 0, 0 ],
            [ 0, 0, 1 ],
            [ 0, 0, 0 ] ]
 
    # Function call
    print(numSpecial(mat))
 
# This code is contributed by Amit Katiyar

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count required 1s
// from the given matrix
static int numSpecial(int [,]mat)
{
     
    // Stores the dimensions of the [,]mat
    int m = mat.GetLength(0);
    int n = mat.GetLength(1);
  
    int []rows = new int[m];
    int []cols = new int[n];
  
    int i, j;
  
    // Calculate sum of rows
    for(i = 0; i < m; i++)
    {
        rows[i] = 0;
         
        for(j = 0; j < n; j++)
            rows[i] += mat[i, j];
    }
  
    // Calculate sum of columns
    for(i = 0; i < n; i++)
    {
        cols[i] = 0;
         
        for(j = 0; j < m; j++)
            cols[i] += mat[j, i];
    }
  
    // Stores required count of 1s
    int cnt = 0;
     
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
             
            // If current cell is 1 and
            // sum of row and column is 1
            if (mat[i, j] == 1 &&
                  rows[i] == 1 &&
                  cols[j] == 1)
  
                // Increment count of 1s
                cnt++;
        }
    }
     
    // Return the readonly count
    return cnt;
}
  
// Driver Code
public static void Main(String[] args)
{
     
    // Given matrix
    int [,]mat = { { 1, 0, 0 },
                   { 0, 0, 1 },
                   { 0, 0, 0 } };
  
    // Function call
    Console.Write(numSpecial(mat) + "\n");
}
}
  
// This code is contributed by Amit Katiyar

<script>
// javascript program for the above approach
 
// Function to count required 1s
// from the given matrix
function numSpecial(mat)
{
     
    // Stores the dimensions of the mat
    var m = mat.length;
    var n = mat[0].length;
  
    var rows = Array.from({length: m}, (_, i) => 0);
    var cols = Array.from({length: n}, (_, i) => 0);
    var i, j;
  
    // Calculate sum of rows
    for(i = 0; i < m; i++)
    {
        rows[i] = 0;
         
        for(j = 0; j < n; j++)
            rows[i] += mat[i][j];
    }
  
    // Calculate sum of columns
    for(i = 0; i < n; i++)
    {
        cols[i] = 0;
         
        for(j = 0; j < m; j++)
            cols[i] += mat[j][i];
    }
  
    // Stores required count of 1s
    var cnt = 0; 
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
             
            // If current cell is 1
            // and sum of row and column is 1
            if (mat[i][j] == 1 &&
                  rows[i] == 1 &&
                  cols[j] == 1)
  
                // Increment count of 1s
                cnt++;
        }
    }
     
    // Return the final count
    return cnt;
}
  
// Driver Code
 
// Given matrix
    var mat = [ [ 1, 0, 0 ],
                    [ 0, 0, 1 ],
                    [ 0, 0, 0 ] ];
  
// Function call
document.write(numSpecial(mat) + "\n");
 
// This code is contributed by Amit Katiyar
</script>

2

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 dos arrays, fila y columna.