Dada una array booleana mat[][] de tamaño M * N, la tarea es imprimir el recuento de índices de la array cuya fila y columna correspondientes contienen un número igual de bits establecidos.
Ejemplos:
Aporte; mat[][] = {{0, 1}, {1, 1}}
Salida : 2
Explicación:
La posición (0, 0) contiene 1 bit establecido en la fila correspondiente {(0, 0), (0, 1)} y columna {(0, 0), (1, 0)}.
La posición (1, 1) contiene 2 bits establecidos en la fila correspondiente {(1, 0), (1, 1)} y columna {(0, 1), (1, 1)}.Entrada: mat[][] = {{0, 1, 1, 0}, {0, 1, 0, 0}, {1, 0, 1, 0}}
Salida: 5
Enfoque ingenuo: el enfoque más simple para resolver es contar y almacenar el número de bits establecidos presentes en los elementos de cada fila y columna de la array dada. Luego, recorra la array y para cada posición, verifique si el recuento de bits establecidos tanto de la fila como de la columna es igual o no. Para cada índice para el que se descubra que la condición anterior es verdadera, incremente count . Imprime el valor final de la cuenta después de completar el recorrido de la array.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación:
- Inicialice dos arrays temporales fila[] y col[] de tamaños N y M respectivamente.
- Atraviesa la array mat[][] . Compruebe para cada índice (i, j) , si mat[i][j] es igual a 1 o no. Si se determina que es cierto, incremente la fila[i] y la columna[j] en 1 .
- Atraviese la array mat[][] de nuevo. Verifique para cada índice (i, j) , si la fila [i] y la columna [j] son iguales o no. Si se encuentra que es verdadero, incremente el conteo.
- Imprime el valor final de count .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of indices in
// from the given binary matrix having equal
// count of set bits in its row and column
int countPosition(vector<vector<int>> mat)
{
int n = mat.size();
int m = mat[0].size();
// Stores count of set bits in
// corresponding column and row
vector<int> row(n);
vector<int> col(m);
// Traverse matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// Since 1 contains a set bit
if (mat[i][j] == 1)
{
// Update count of set bits
// for current row and col
col[j]++;
row[i]++;
}
}
}
// Stores the count of
// required indices
int count = 0;
// Traverse matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// If current row and column
// has equal count of set bits
if (row[i] == col[j])
{
count++;
}
}
}
// Return count of
// required position
return count;
}
// Driver Code
int main()
{
vector<vector<int>> mat = { { 0, 1 },
{ 1, 1 } };
cout << (countPosition(mat));
}
// This code is contributed by mohit kumar 29
Java
// Java Program to implement
// above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to return the count of indices in
// from the given binary matrix having equal
// count of set bits in its row and column
static int countPosition(int[][] mat)
{
int n = mat.length;
int m = mat[0].length;
// Stores count of set bits in
// corresponding column and row
int[] row = new int[n];
int[] col = new int[m];
// Traverse matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Since 1 contains a set bit
if (mat[i][j] == 1) {
// Update count of set bits
// for current row and col
col[j]++;
row[i]++;
}
}
}
// Stores the count of
// required indices
int count = 0;
// Traverse matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// If current row and column
// has equal count of set bits
if (row[i] == col[j]) {
count++;
}
}
}
// Return count of
// required position
return count;
}
// Driver Code
public static void main(
String[] args)
{
int mat[][] = { { 0, 1 },
{ 1, 1 } };
System.out.println(
countPosition(mat));
}
}
Python3
# Python3 program to implement # the above approach # Function to return the count # of indices in from the given # binary matrix having equal # count of set bits in its # row and column def countPosition(mat): n = len(mat) m = len(mat[0]) # Stores count of set bits in # corresponding column and row row = [0] * n col = [0] * m # Traverse matrix for i in range(n): for j in range(m): # Since 1 contains a set bit if (mat[i][j] == 1): # Update count of set bits # for current row and col col[j] += 1 row[i] += 1 # Stores the count of # required indices count = 0 # Traverse matrix for i in range(n): for j in range(m): # If current row and column # has equal count of set bits if (row[i] == col[j]): count += 1 # Return count of # required position return count # Driver Code mat = [ [ 0, 1 ], [ 1, 1 ] ] print(countPosition(mat)) # This code is contributed by sanjoy_62
C#
// C# Program to implement
// above approach
using System;
class GFG{
// Function to return the count of indices in
// from the given binary matrix having equal
// count of set bits in its row and column
static int countPosition(int[,] mat)
{
int n = mat.GetLength(0);
int m = mat.GetLength(1);
// Stores count of set bits in
// corresponding column and row
int[] row = new int[n];
int[] col = new int[m];
// Traverse matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// Since 1 contains a set bit
if (mat[i, j] == 1)
{
// Update count of set bits
// for current row and col
col[j]++;
row[i]++;
}
}
}
// Stores the count of
// required indices
int count = 0;
// Traverse matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// If current row and column
// has equal count of set bits
if (row[i] == col[j])
{
count++;
}
}
}
// Return count of
// required position
return count;
}
// Driver Code
public static void Main(String[] args)
{
int [,]mat = {{0, 1},
{1, 1}};
Console.WriteLine(countPosition(mat));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// above approach
// Function to return the count of indices in
// from the given binary matrix having equal
// count of set bits in its row and column
function countPosition(mat)
{
var n = mat.length;
var m = mat[0].length;
// Stores count of set bits in
// corresponding column and row
var row = Array.from({length: n}, (_, i) => 0);
var col = Array.from({length: m}, (_, i) => 0);
// Traverse matrix
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Since 1 contains a set bit
if (mat[i][j] == 1)
{
// Update count of set bits
// for current row and col
col[j]++;
row[i]++;
}
}
}
// Stores the count of
// required indices
var count = 0;
// Traverse matrix
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// If current row and column
// has equal count of set bits
if (row[i] == col[j])
{
count++;
}
}
}
// Return count of
// required position
return count;
}
// Driver Code
var mat = [ [ 0, 1 ],
[ 1, 1 ] ];
document.write(countPosition(mat));
// This code is contributed by Rajput-Ji
</script>
Producción:
2
Complejidad temporal: O(N * M)
Espacio auxiliar: O(N+M)