Encuentre si existe una array binaria con sumas de filas y columnas dadas

Posted on by Rudeus Greyrat

Dada una array Fila[] de tamaño R donde Fila[i] es la suma de elementos de la i -ésima fila y otra array Columna[] de tamaño C donde Columna[i] es la suma de elementos de la i -ésima columna. La tarea es verificar si es posible construir una array binaria de dimensión R * C que satisfaga las sumas de filas y las sumas de columnas dadas. Una array binaria es una array que se llena solo con 0 y 1. 
Suma significa el número de 1 en una fila o columna en particular.
Ejemplos: 
 

Entrada: Fila[] = {2, 2, 2, 2, 2}, Columna[] = {5, 5, 0, 0} 
Salida: SÍ 
La array es 
{1, 1, 0, 0} 
{1, 1, 0, 0} 
{1, 1, 0, 0} 
{1, 1, 0, 0} 
{1, 1, 0, 0}
Entrada: Fila[] = {0, 0, 3} Columna[] = {3 , 0, 0} 
Salida: NO 
 

Acercarse: 
 

  1. La idea clave es que cualquier celda de la array contribuirá por igual a la suma de las filas y las columnas, por lo que la suma de todas las sumas de las filas debe ser igual a la suma de las columnas.
  2. Ahora, encuentre el máximo de sumas de filas, si este valor es mayor que el número de sumas de columnas distintas de cero, entonces la array no existe.
  3. Si el máximo de sumas de columnas es mayor que el número de sumas de filas distintas de cero, entonces no es posible construir una array.
  4. Si se cumplen las 3 condiciones anteriores, entonces existe la array.

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if matrix exists
bool matrix_exist(int row[], int column[], int r, int c)
{
    int row_sum = 0;
    int column_sum = 0;
    int row_max = -1;
    int column_max = -1;
    int row_non_zero = 0;
    int column_non_zero = 0;
 
    // Store sum of rowsums, max of row sum
    // number of non zero row sums
    for (int i = 0; i < r; i++) {
        row_sum += row[i];
        row_max = max(row_max, row[i]);
        if (row[i])
            row_non_zero++;
    }
 
    // Store sum of column sums, max of column sum
    // number of non zero column sums
    for (int i = 0; i < c; i++) {
        column_sum += column[i];
        column_max = max(column_max, column[i]);
        if (column[i])
            column_non_zero++;
    }
 
    // Check condition 1, 2, 3
    if ((row_sum != column_sum) ||
        (row_max > column_non_zero) ||
        (column_max > row_non_zero))
        return false;
 
    return true;
}
 
// Driver Code
int main()
{
    int row[] = { 2, 2, 2, 2, 2 };
    int column[] = { 5, 5, 0, 0 };
    int r = sizeof(row) / sizeof(row[0]);
    int c = sizeof(column) / sizeof(column[0]);
 
    if (matrix_exist(row, column, r, c))
        cout << "YES\n";
    else
        cout << "NO\n";
}

Java

// Java implementation of above approach
import java.util.*;
 
class GFG
{
 
    // Function to check if matrix exists
    static boolean matrix_exist(int row[], int column[],
                                        int r, int c)
    {
        int row_sum = 0;
        int column_sum = 0;
        int row_max = -1;
        int column_max = -1;
        int row_non_zero = 0;
        int column_non_zero = 0;
 
        // Store sum of rowsums, max of row sum
        // number of non zero row sums
        for (int i = 0; i < r; i++)
        {
            row_sum += row[i];
            row_max = Math.max(row_max, row[i]);
            if (row[i] > 0)
            {
                row_non_zero++;
            }
        }
 
        // Store sum of column sums, max of column sum
        // number of non zero column sums
        for (int i = 0; i < c; i++)
        {
            column_sum += column[i];
            column_max = Math.max(column_max, column[i]);
            if (column[i] > 0)
            {
                column_non_zero++;
            }
        }
 
        // Check condition 1, 2, 3
        if ((row_sum != column_sum)
                || (row_max > column_non_zero)
                || (column_max > row_non_zero))
        {
            return false;
        }
 
        return true;
    }
 
// Driver Code
public static void main(String[] args)
{
    int row[] = { 2, 2, 2, 2, 2 };
    int column[] = { 5, 5, 0, 0 };
    int r = row.length;
    int c = column.length;
 
    if (matrix_exist(row, column, r, c))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python implementation of the above approach
 
# Function to check if matrix exists
def matrix_exist(row,  column,  r, c):
 
    row_sum = 0
    column_sum = 0
    row_max = -1
    column_max = -1
    row_non_zero = 0
    column_non_zero = 0
 
    # Store sum of rowsums, max of row sum
    # number of non zero row sums
    for i in range(r):
        row_sum += row[i]
        row_max = max(row_max, row[i])
        if (row[i]):
            row_non_zero = row_non_zero + 1
 
    # Store sum of column sums, max of column sum
    # number of non zero column sums
    for i in range(c):
        column_sum = column_sum + column[i]
        column_max = max(column_max, column[i])
        if (column[i]):
            column_non_zero = column_non_zero + 1
 
    # Check condition 1, 2, 3
    if ((row_sum != column_sum)
        or (row_max > column_non_zero)
        or (column_max > row_non_zero)):
         
        return False
 
    return True
 
# Driver Code
if __name__ == '__main__':
    row = [2, 2, 2, 2, 2]
    column = [5, 5, 0, 0]
    r = len(row)
    c = len(column)
    if matrix_exist(row, column, r, c):
        print("YES")
 
    else:
        print("NO")
 
# this code is contributed by nirajgusain5

C#

// C# implementation of above approach
using System;
 
public class GFG{
 
    // Function to check if matrix exists
    static bool matrix_exist(int[] row, int[] column,
                                        int r, int c)
    {
        int row_sum = 0;
        int column_sum = 0;
        int row_max = -1;
        int column_max = -1;
        int row_non_zero = 0;
        int column_non_zero = 0;
 
        // Store sum of rowsums, max of row sum
        // number of non zero row sums
        for (int i = 0; i < r; i++)
        {
            row_sum += row[i];
            row_max = Math.Max(row_max, row[i]);
            if (row[i] > 0)
            {
                row_non_zero++;
            }
        }
 
        // Store sum of column sums, max of column sum
        // number of non zero column sums
        for (int i = 0; i < c; i++)
        {
            column_sum += column[i];
            column_max = Math.Max(column_max, column[i]);
            if (column[i] > 0)
            {
                column_non_zero++;
            }
        }
 
        // Check condition 1, 2, 3
        if ((row_sum != column_sum)
                || (row_max > column_non_zero)
                || (column_max > row_non_zero))
        {
            return false;
        }
 
        return true;
    }
 
    // Driver Code
    static public void Main ()
    {
        int[] row = { 2, 2, 2, 2, 2 };
        int[] column = { 5, 5, 0, 0 };
        int r = row.Length;
        int c = column.Length;
     
        if (matrix_exist(row, column, r, c))
            Console.Write("YES");
        else
            Console.Write("NO");
    }
}
 
// This code has been contributed by shubhamsingh10

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to check if matrix exists
function matrix_exist(row, column, r, c)
{
    var row_sum = 0;
    var column_sum = 0;
    var row_max = -1;
    var column_max = -1;
    var row_non_zero = 0;
    var column_non_zero = 0;
 
    // Store sum of rowsums, max of row sum
    // number of non zero row sums
    for (var i = 0; i < r; i++) {
        row_sum += row[i];
        row_max = Math.max(row_max, row[i]);
        if (row[i])
            row_non_zero++;
    }
 
    // Store sum of column sums, max of column sum
    // number of non zero column sums
    for (var i = 0; i < c; i++) {
        column_sum += column[i];
        column_max = Math.max(column_max, column[i]);
        if (column[i])
            column_non_zero++;
    }
 
    // Check condition 1, 2, 3
    if ((row_sum != column_sum) ||
        (row_max > column_non_zero) ||
        (column_max > row_non_zero))
        return false;
 
    return true;
}
 
// Driver Code
var row = [2, 2, 2, 2, 2];
var column = [5, 5, 0, 0];
var r = row.length;
var c = column.length;
if (matrix_exist(row, column, r, c))
    document.write( "YES");
else
    document.write( "NO");
 
</script>
Producción: 

YES

 

Complejidad de tiempo : O(N)
 

Publicación traducida automáticamente

Artículo escrito por krikti 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 *