Dada una array binaria de tamaño M*N que contiene solo 0 y 1 . La tarea es contar el número de asignaciones en la array. Hay un mapeo entre dos 1 s cualesquiera si se cumplen las siguientes condiciones:
- Los dos 1 están ubicados en dos filas diferentes: r1 y r2 , donde r1 < r2 .
- Para cada fila i donde r1 < i < r2 , no hay 1 en la i-ésima fila.
Ejemplos:
Entrada: array[][] = { {0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0} ,
{0, 0, 1, 0, 0, 0} };
Salida: 8
Explicación: Entre cada uno de los siguientes 1, hay una asignación. En total, hay 8 asignaciones:
array[0][1] -> array[2][1]
array[0][1] -> array[2][3]
array[0][2] -> array [2][1]
array[0][2] -> array[2][3]
array[0][5] -> array[2][1]
array[0][5] -> array[2 ][3]
array[2][1] -> array[3][2]
array[2][3] -> array[3][2]
Tenga en cuenta que no hay asignación entre ningún 1 en la fila 0 con cualquiera en la 3ra fila.
Esto se debe a que la segunda fila contiene 1, lo que rompe la segunda condición.Entrada: array = { {0, 0, 0},
{1, 1, 1},
{0, 0, 0} };
Salida: 0
Explicación: No existen dos 1 ubicados en dos filas diferentes.
Enfoque: La idea es atravesar cada fila y contar el número de 1 s en ella. Recorra las filas subsiguientes y deténgase cuando la primera fila siguiente contenga al menos un 1 . Calcule el número de asignaciones entre estas dos filas y agréguelas a la variable de suma . Nuevamente, repita este proceso haciendo que la última fila sea el punto de referencia inicial. Siga los pasos a continuación para resolver el problema dado.
- Considere la primera fila como la fila anterior y cuente los 1 en ella, es decir, prev = recuento de 1 en la primera fila.
- Cuente 1 s en las filas subsiguientes y deténgase cuando una fila tenga al menos un 1 , es decir, siguiente = conteo de 1 en la fila subsiguiente.
- Calcule las asignaciones entre la fila anterior y la siguiente, es decir , maps = anterior * siguiente
- Agregue el número de nuevas asignaciones en la variable de suma, es decir, res += mapas.
- Haga la siguiente fila como la anterior y repita el ciclo de encontrar la siguiente fila.
- Finalmente, imprima el número de asignaciones totales .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <iostream>
#include <vector>
using namespace std;
// Function to count the number of mappings
int CountNumberOfMappings(vector<vector<int> >& matrix)
{
int i, j, prev = 0, m = matrix.size(),
n = matrix[0].size();
// Count 1s in first row.
for (i = 0; i < n; i++) {
if (matrix[0][i] == 1)
prev += 1;
}
// Count 1s in subsequent rows.
int next = 0, res = 0;
for (j = 1; j < m; j++) {
next = 0;
for (i = 0; i < n; i++) {
if (matrix[j][i] == 1)
next += 1;
}
// Stop when a row has
// atleast one 1 in it.
if (next > 0) {
// Compute number of mappings
// between prev and next rows.
res += prev * next;
// Add these mappings to
// result variable.
prev = next;
}
}
// Return total number of mappings.
return res;
}
// Driver Code
int main()
{
vector<vector<int> > matrix{ { 0, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 } };
int res = CountNumberOfMappings(matrix);
cout << res;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Function to count the number of mappings
static int CountNumberOfMappings(int[][] matrix)
{
int i, j, prev = 0, m = matrix.length,
n = matrix[0].length;
// Count 1s in first row.
for (i = 0; i < n; i++) {
if (matrix[0][i] == 1)
prev += 1;
}
// Count 1s in subsequent rows.
int next = 0, res = 0;
for (j = 1; j < m; j++) {
next = 0;
for (i = 0; i < n; i++) {
if (matrix[j][i] == 1)
next += 1;
}
// Stop when a row has
// atleast one 1 in it.
if (next > 0)
{
// Compute number of mappings
// between prev and next rows.
res += prev * next;
// Add these mappings to
// result variable.
prev = next;
}
}
// Return total number of mappings.
return res;
}
// Driver Code
public static void main (String[] args) {
int[][] matrix = { { 0, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 } };
int res = CountNumberOfMappings(matrix);
System.out.print(res);
}
}
// This code is contributed by hrithikgarg03188
Python3
# Python code for the above approach # Function to count the number of mappings def CountNumberOfMappings(matrix): prev = 0 m = len(matrix) n = len(matrix[0]) # Count 1s in first row. for i in range(n): if (matrix[0][i] == 1): prev += 1 # Count 1s in subsequent rows. next = 0 res = 0 for j in range(1, m): next = 0 for i in range(n): if (matrix[j][i] == 1): next += 1 # Stop when a row has # atleast one 1 in it. if (next > 0): # Compute number of mappings # between prev and next rows. res += prev * next # Add these mappings to # result variable. prev = next # Return total number of mappings. return res # Driver Code matrix = [[0, 1, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0]] res = CountNumberOfMappings(matrix) print(res) # This code is contributed by gfgking
C#
// C# program for above approach
using System;
class GFG
{
// Function to count the number of mappings
static int CountNumberOfMappings(int[, ] matrix)
{
int prev = 0;
int m = matrix.GetLength(0), n
= matrix.GetLength(1);
// Count 1s in first row.
for (int i = 0; i < n; i++) {
if (matrix[0, i] == 1)
prev += 1;
}
// Count 1s in subsequent rows.
int next = 0, res = 0;
for (int j = 1; j < m; j++) {
next = 0;
for (int i = 0; i < n; i++) {
if (matrix[j, i] == 1)
next += 1;
}
// Stop when a row has
// atleast one 1 in it.
if (next > 0) {
// Compute number of mappings
// between prev and next rows.
res += prev * next;
// Add these mappings to
// result variable.
prev = next;
}
}
// Return total number of mappings.
return res;
}
// Driver Code
public static void Main()
{
int[, ] matrix = { { 0, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 } };
int res = CountNumberOfMappings(matrix);
Console.Write(res);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to count the number of mappings
function CountNumberOfMappings(matrix) {
let i, j, prev = 0, m = matrix.length,
n = matrix[0].length;
// Count 1s in first row.
for (i = 0; i < n; i++) {
if (matrix[0][i] == 1)
prev += 1;
}
// Count 1s in subsequent rows.
let next = 0, res = 0;
for (j = 1; j < m; j++) {
next = 0;
for (i = 0; i < n; i++) {
if (matrix[j][i] == 1)
next += 1;
}
// Stop when a row has
// atleast one 1 in it.
if (next > 0) {
// Compute number of mappings
// between prev and next rows.
res += prev * next;
// Add these mappings to
// result variable.
prev = next;
}
}
// Return total number of mappings.
return res;
}
// Driver Code
let matrix = [[0, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0]];
let res = CountNumberOfMappings(matrix);
document.write(res);
// This code is contributed by Potta Lokesh
</script>
8
Complejidad temporal: O(M*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA