Recuento de rectángulos con área K formado por solo 1 de arrays binarias dadas

Dadas dos arrays binarias A[] y B[] , de longitud N y M respectivamente, la tarea es encontrar el número de rectángulos de área K que consisten en 1 en la array C[][] generada al multiplicar las dos arrays tal que, C[i][j] = A[i] * B[j] (1 < i < n, 1 < j < m).

Ejemplos:

Entrada: N= 3, M = 3, A[] = {1, 1, 0}, B[] = {0, 1, 1}, K = 2 Salida: 4 Explicación: C[][ 
]
{ { 0, 1, 1}, {0, 1, 1}, {0, 0, 0}}

0 1 1        0 1 1      0 1 1       0 1 1
0 1 1        0 1 1      0 1 1       0 1 1
0 0 0        0 0 0      0 0 0       0 0 0

Por lo tanto, hay 4 posibles rectángulos de área 2 de la array.
Entrada: N = 4, M = 2, A[] = {0, 0, 1, 1}, B[] = {1, 0, 1}, K = 2 Salida: 2 Explicación: C[ 
]
] = {{0, 0, 0}, {0, 0, 0}, {1, 0, 1}, {1, 0, 1}} 

0 0 0        0 0 0
0 0 0        0 0 0
1 0 1        1 0 1
1 0 1        1 0 1

Por lo tanto, hay 2 posibles rectángulos de área 2 en la array. 

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar la array requerida multiplicando las dos arrays y para cada rectángulo posible del área K, verifique si consta solo de 1 o no. 
Complejidad de Tiempo: O(N * M * K) 
Espacio Auxiliar: O(N * M)

Enfoque eficiente: para optimizar el enfoque anterior, se deben realizar las siguientes observaciones en lugar de generar la array: 

  • El área de un rectángulo es igual al producto de su largo por su ancho.
  • Usando esta propiedad, visualice el rectángulo como una subarray que contiene solo 1 s. Por tanto, esta subarray es el resultado del producto de dos subarreglos de longitud a, b donde a * b = K .
  • Dado que la subarray contiene solo 1 , es obvio que estos dos subarreglos también contienen solo 1 .

Por lo tanto, el problema se reduce a encontrar los subarreglos que consisten en solo 1 de todas las longitudes posibles que son divisores propios de K , de los arreglos A[] y B[] . Siga los pasos a continuación para resolver el problema:

  • Precalcular el recuento de posibles subarreglos .
  • Iterar a través de todos los divisores de K y para cada par posible ( p, q ) donde p * q = K , verifique si existen subarreglos de longitud p, q en A[] y B[].
  • Aumente el recuento de posibles subarreglos en consecuencia y, finalmente, imprima el recuento obtenido.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the subarrays of
// all possible lengths made up of only 1s
vector<int> findSubarrays(vector<int>& a)
{
    int n = a.size();
 
    // Stores the frequency
    // of the subarrays
    vector<int> freq(n + 1);
 
    int count = 0;
 
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
 
            // Check if the previous
            // value was also 0
            if (count == 0)
                continue;
 
            // If the previous value was 1
            else {
 
                int value = count;
                for (int j = 1; j <= count; j++) {
 
                    // Find the subarrays of
                    // each size from 1 to count
                    freq[j] += value;
                    value--;
                }
 
                count = 0;
            }
        }
 
        else
            count++;
    }
 
    // If A[] is of the form ....111
    if (count > 0) {
        int value = count;
        for (int j = 1; j <= count; j++) {
            freq[j] += value;
            value--;
        }
    }
 
    return freq;
}
 
// Function to find the count
// of all possible rectangles
void countRectangles(vector<int>& a,
                     vector<int>& b, int K)
{
    // Size of each of the arrays
    int n = a.size();
 
    int m = b.size();
 
    // Stores the count of subarrays
    // of each size consisting of
    // only 1s from array A[]
 
    vector<int> subA
        = findSubarrays(a);
 
    // Stores the count of subarrays
    // of each size consisting of
    // only 1s from array B[]
    vector<int> subB
        = findSubarrays(b);
 
    int total = 0;
 
    // Iterating over all subarrays
    // consisting of only 1s in A[]
    for (int i = 1; i < subA.size(); i++) {
 
        // If i is a factor of K, then
        // there is a subarray of size K/i in B[]
        if (K % i == 0 and (K / i) <= m) {
            total = total + subA[i] * subB[K / i];
        }
    }
 
    cout << total;
}
 
// Driver Code
int main()
{
    vector<int> a = { 0, 0, 1, 1 };
 
    vector<int> b = { 1, 0, 1 };
    int K = 2;
 
    countRectangles(a, b, K);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
class GFG{
 
    // Function to find the subarrays of
    // all possible lengths made up of only 1s
    static int[] findSubarrays(int[] a)
    {
        int n = a.length;
 
        // Stores the frequency
        // of the subarrays
        int[] freq = new int[n + 1];
        int count = 0;
          for (int i = 0; i < n; i++)
        {
            if (a[i] == 0)
            {
 
                // Check if the previous
                // value was also 0
                if (count == 0)
                    continue;
 
                // If the previous value was 1
                else
                {
                    int value = count;
                    for (int j = 1; j <= count; j++)
                    {
 
                        // Find the subarrays of
                        // each size from 1 to count
                        freq[j] += value;
                        value--;
                    }
                    count = 0;
                }
            }
            else
                count++;
        }
 
        // If A[] is of the form ....111
        if (count > 0)
        {
            int value = count;
            for (int j = 1; j <= count; j++)
            {
                freq[j] += value;
                value--;
            }
        }
        return freq;
    }
 
    // Function to find the count
    // of all possible rectangles
    static void countRectangles(int[] a, int[] b, int K)
    {
        // Size of each of the arrays
        int n = a.length;
        int m = b.length;
 
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array A[]
        int[] subA = findSubarrays(a);
 
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array B[]
        int[] subB = findSubarrays(b);
 
        int total = 0;
 
        // Iterating over all subarrays
        // consisting of only 1s in A[]
        for (int i = 1; i < subA.length; i++)
        {
 
            // If i is a factor of K, then
            // there is a subarray of size K/i in B[]
            if (K % i == 0 && (K / i) <= m)
            {
                total = total + subA[i] * subB[K / i];
            }
        }
        System.out.print(total);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] a = {0, 0, 1, 1};
        int[] b = {1, 0, 1};
        int K = 2;
        countRectangles(a, b, K);
    }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program to implement
# the above approach
 
# Function to find the subarrays of
# all possible lengths made up of only 1s
def findSubarrays(a):
 
    n = len(a)
 
    # Stores the frequency
    # of the subarrays
    freq = [0] * (n + 1)
 
    count = 0
 
    for i in range(n):
        if (a[i] == 0):
 
            # Check if the previous
            # value was also 0
            if (count == 0):
                continue
 
            # If the previous value was 1
            else:
                value = count
                for j in range(1, count + 1):
 
                    # Find the subarrays of
                    # each size from 1 to count
                    freq[j] += value
                    value -= 1
                 
                count = 0
                 
        else:
            count += 1
     
    # If A[] is of the form ....111
    if (count > 0):
        value = count
        for j in range(1, count + 1):
            freq[j] += value
            value -= 1
         
    return freq
 
# Function to find the count
# of all possible rectangles
def countRectangles(a, b, K):
 
    # Size of each of the arrays
    n = len(a)
    m = len(b)
 
    # Stores the count of subarrays
    # of each size consisting of
    # only 1s from array A[]
    subA = []
    subA = findSubarrays(a)
 
    # Stores the count of subarrays
    # of each size consisting of
    # only 1s from array B[]
    subB = []
    subB = findSubarrays(b)
 
    total = 0
 
    # Iterating over all subarrays
    # consisting of only 1s in A[]
    for i in range(1, len(subA)):
         
        # If i is a factor of K, then
        # there is a subarray of size K/i in B[]
        if (K % i == 0 and (K // i) <= m):
            total = total + subA[i] * subB[K // i]
         
    print(total)
 
# Driver Code
a = [ 0, 0, 1, 1 ]
b = [ 1, 0, 1 ]
 
K = 2
 
countRectangles(a, b, K)
 
# This code is contributed by code_hunt

C#

// C# Program to implement
// the above approach
using System;
class GFG{
 
    // Function to find the subarrays of
    // all possible lengths made up of only 1s
    static int[] findSubarrays(int[] a)
    {
        int n = a.Length;
 
        // Stores the frequency
        // of the subarrays
        int[] freq = new int[n + 1];
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 0)
            {
                // Check if the previous
                // value was also 0
                if (count == 0)
                    continue;
 
                // If the previous value was 1
                else
                {
                    int value = count;
                    for (int j = 1; j <= count; j++)
                    {
                        // Find the subarrays of
                        // each size from 1 to count
                        freq[j] += value;
                        value--;
                    }
                    count = 0;
                }
            }
            else
                count++;
        }
 
        // If []A is of the form ....111
        if (count > 0)
        {
            int value = count;
            for (int j = 1; j <= count; j++)
            {
                freq[j] += value;
                value--;
            }
        }
        return freq;
    }
 
    // Function to find the count
    // of all possible rectangles
    static void countRectangles(int[] a, int[] b,
                                int K)
    {
        // Size of each of the arrays
        int n = a.Length;
        int m = b.Length;
 
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array []A
        int[] subA = findSubarrays(a);
 
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array []B
        int[] subB = findSubarrays(b);
 
        int total = 0;
 
        // Iterating over all subarrays
        // consisting of only 1s in []A
        for (int i = 1; i < subA.Length; i++)
        {
 
            // If i is a factor of K, then
            // there is a subarray of size K/i in []B
            if (K % i == 0 && (K / i) <= m)
            {
                total = total + subA[i] *
                        subB[K / i];
            }
        }
        Console.Write(total);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = {0, 0, 1, 1};
        int[] b = {1, 0, 1};
        int K = 2;
        countRectangles(a, b, K);
    }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program to implement
// the above approach
     
    // Function to find the subarrays of
    // all possible lengths made up of only 1s
    function findSubarrays(a)
    {
        let n = a.length;
   
        // Stores the frequency
        // of the subarrays
        let freq = new Array(n+1).fill(0);
        let count = 0;
          for (let i = 0; i < n; i++)
        {
            if (a[i] == 0)
            {
   
                // Check if the previous
                // value was also 0
                if (count == 0)
                    continue;
   
                // If the previous value was 1
                else
                {
                    let value = count;
                    for (let j = 1; j <= count; j++)
                    {
   
                        // Find the subarrays of
                        // each size from 1 to count
                        freq[j] += value;
                        value--;
                    }
                    count = 0;
                }
            }
            else
                count++;
        }
   
        // If A[] is of the form ....111
        if (count > 0)
        {
            let value = count;
            for (let j = 1; j <= count; j++)
            {
                freq[j] += value;
                value--;
            }
        }
        return freq;
    }
   
    // Function to find the count
    // of all possible rectangles
    function countRectangles(a, b, K)
    {
        // Size of each of the arrays
        let n = a.length;
        let m = b.length;
   
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array A[]
        let subA = findSubarrays(a);
   
        // Stores the count of subarrays
        // of each size consisting of
        // only 1s from array B[]
        let subB = findSubarrays(b);
   
        let total = 0;
   
        // Iterating over all subarrays
        // consisting of only 1s in A[]
        for (let i = 1; i < subA.length; i++)
        {
   
            // If i is a factor of K, then
            // there is a subarray of size K/i in B[]
            if (K % i == 0 && (K / i) <= m)
            {
                total = total + subA[i] * subB[K / i];
            }
        }
        document.write(total);
    }
 
// Driver Code
 
        let a = [0, 0, 1, 1];
        let b = [1, 0, 1];
        let K = 2;
        countRectangles(a, b, K);
     
</script>
Producción: 

2

Complejidad Temporal: O(D) * O(N + M), donde D es el número de divisores de K. 
Espacio Auxiliar: O(N + M)

Publicación traducida automáticamente

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