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 0Por 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 1Por 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