Dada una array de números positivos y un número k, encuentre la cantidad de subarreglos que tienen un producto exactamente igual a k. Podemos suponer que no hay desbordamiento.
Ejemplos:
Input : arr = [2, 1, 1, 1, 4, 5]
k = 4
Output : 4
1st subarray : arr[1..4]
2nd subarray : arr[2..4]
3rd subarray : arr[3..4]
4th subarray : arr[4]
Input : arr = [1, 2, 3, 4, 1]
k = 24
Output : 4
1st subarray : arr[0..4]
2nd subarray : arr[1..4]
3rd subarray : arr[1..3]
4th subarray : arr[0..3]
Una solución simple es considerar todos los subarreglos y encontrar sus productos. Para cada producto, compruebe si es igual a k. En caso afirmativo, aumente el resultado.
Una solución eficiente es utilizar la técnica de ventana deslizante para resolver el problema. Usamos dos punteros, inicio y fin, para representar el punto inicial y final de la ventana deslizante.
Inicialmente, tanto el inicio como el final apuntan al comienzo de la array, es decir, el índice 0. Continúe incrementando el final hasta que el producto p < k. Tan pronto como p sea igual a k, deje de incrementar end y verifique si la posición actual de end está seguida por una serie de 1 en la array. En caso afirmativo, esos 1 también contribuirán al recuento del subarreglo. Almacene el recuento de estos 1 sucesivos en una variable countOnes. Después de esto, siga incrementando el inicio hasta que p sea igual a k mientras agrega (countOnes + 1) al resultado. Si el inicio coincide con el final, comience nuevamente desde el final incremental y siga el mismo procedimiento. Haga esto hasta el final <tamaño de la array.
¿Por qué se agrega countOnes + 1 al resultado?
Considere el segundo caso de prueba en los casos de muestra anteriores. Si seguimos el procedimiento mencionado anteriormente, luego de incrementar end, llegaremos a start = 0 y end = 3. Después de esto, countOnes se establece en 1. ¿Cuántos subarreglos hay para start = 0? Hay dos subarreglos: arr[0..3] y arr[0..4]. Observe que subarreglo[0..3] es lo que hemos encontrado usando la técnica de ventana deslizante. Esto aumenta el recuento de resultados en 1 y es lo que representa + 1 en la expresión countOnes + 1. El otro subarreglo [0..4] se obtiene simplemente agregando un solo 1 al subarreglo [0..3], es decir, sumando el número de countOnes de 1s uno a la vez. Intentemos generalizarlo. Suponga que arr[0..i] es el subarreglo obtenido mediante la técnica de ventana deslizante y sea countOnes = j. Luego, podemos expandir este subarreglo por unidad de longitud a la vez agregando un solo 1 a este subarreglo.
Por lo tanto, el recuento de resultados aumenta en countOnes y se representa como countOnes en la expresión countOnes + 1. Por lo tanto, para cada incremento en start hasta que p sea igual a k, simplemente agregue countOnes + 1 al resultado.
Tenga en cuenta que el algoritmo anterior no funcionará para el caso cuando k = 1. Por ejemplo, considere el caso de prueba arr[] = {2, 1, 1, 1}. Gracias a Jeel Santoki por este caso de prueba. Para el caso en que k = 1, encontraremos la longitud de cada segmento de la array en la que todos los elementos son 1. Sea x la longitud de un segmento particular de 1. El número de subarreglos de este segmento será x*(x+1)/2. Todos estos subarreglos tendrán el producto 1 ya que todos los elementos son 1. En el caso de prueba dado, solo hay un segmento de 1 del índice 1 al índice 3 que tiene una longitud de 3. Entonces, los subarreglos totales con el producto 1 son (3 * 4)/2 = 6 .
El algoritmo se puede enumerar como:
For k != 1:
1. Initialize start = end = 0
2. Initialize res = 0, p = 1
3. Increment end until p < k
4. When p = k do:
Set countOnes = number of succeeding ones
res += (countOnes+1)
Increment start until p = k
and do res += (countOnes+1)
5. Stop if end = n
For k = 1:
1. Find all segments in array in which
only 1 is present.
2. Find length of each segment.
3. Add length*(length+1) / 2 to result.
Implementación:
C++
// C++ program to find number of subarrays
// having product exactly equal to k.
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays
// having product equal to 1.
int countOne(int arr[], int n){
int i = 0;
// To store number of ones in
// current segment of all 1s.
int len = 0;
// To store number of subarrays
// having product equal to 1.
int ans = 0;
while(i < n){
// If current element is 1, then
// find length of segment of 1s
// starting from current element.
if(arr[i] == 1){
len = 0;
while(i < n && arr[i] == 1){
i++;
len++;
}
// add number of possible
// subarrays of 1 to result.
ans += (len*(len+1)) / 2;
}
i++;
}
return ans;
}
/// Function to find number of subarrays having
/// product exactly equal to k.
int findSubarrayCount(int arr[], int n, int k)
{
int start = 0, endval = 0, p = 1,
countOnes = 0, res = 0;
while (endval < n)
{
p *= (arr[endval]);
// If product is greater than k then we need to decrease
// it. This could be done by shifting starting point of
// sliding window one place to right at a time and update
// product accordingly.
if(p > k)
{
while(start <= endval && p > k)
{
p /= arr[start];
start++;
}
}
if(p == k)
{
// Count number of succeeding ones.
countOnes = 0;
while(endval + 1 < n && arr[endval + 1] == 1)
{
countOnes++;
endval++;
}
// Update result by adding both new subarray
// and effect of succeeding ones.
res += (countOnes + 1);
// Update sliding window and result according
// to change in sliding window. Here preceding
// 1s have same effect on subarray as succeeding
// 1s, so simply add.
while(start <= endval && arr[start] == 1 && k!=1)
{
res += (countOnes + 1);
start++;
}
// Move start to correct position to find new
// subarray and update product accordingly.
p /= arr[start];
start++;
}
endval++;
}
return res;
}
// Driver code
int main()
{
int arr1[] = { 2, 1, 1, 1, 3, 1, 1, 4};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int k = 1;
if(k != 1)
cout << findSubarrayCount(arr1, n1, k) << "\n";
else
cout << countOne(arr1, n1) << "\n";
int arr2[] = { 2, 1, 1, 1, 4, 5};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
k = 4;
if(k != 1)
cout << findSubarrayCount(arr2, n2, k) << "\n";
else
cout << countOne(arr2, n2) << "\n";
return 0;
}
Java
// Java program to find number of subarrays
// having product exactly equal to k.
import java.util.*;
class GFG
{
// Function to find number of subarrays having
// product exactly equal to k.
public static int findSubarrayCount(int arr[], int n, int k)
{
int start = 0, endval = 0;
int p = 1, countOnes = 0, res = 0;
while(endval < n)
{
p *= (arr[endval]);
// If product is greater than k then we need
// to decrease it. This could be done by shifting
// starting point of sliding window one place
// to right at a time and update product accordingly.
if (p > k)
{
while (start <= endval && p > k)
{
p /= arr[start];
start++;
}
}
if (p == k)
{
// Count number of succeeding ones.
countOnes = 0;
while (endval + 1 < n && arr[endval + 1] == 1)
{
countOnes++;
endval++;
}
// Update result by adding both new
// subarray and effect of succeeding ones.
res += (countOnes + 1);
// Update sliding window and result according
// to change in sliding window. Here preceding
// 1s have same effect on subarray as succeeding
// 1s, so simply add.
while (start <= endval && arr[start] == 1)
{
res += (countOnes + 1);
start++;
}
// Move start to correct position to find new
// subarray and update product accordingly.
p /= arr[start];
start++;
}
endval++;
}
return res;
}
// Driver code
public static void main (String[] args)
{
int arr[] = new int[]{ 2, 1, 1, 1, 4, 5 };
int n = arr.length;
int k = 4;
System.out.println(findSubarrayCount(arr, n, k));
}
}
Python3
# Python3 program to find number of subarrays # having product exactly equal to k. # Function to find number of subarrays # having product equal to 1. def countOne(arr, n) : i = 0 # To store number of ones in # current segment of all 1s. Len = 0 # To store number of subarrays # having product equal to 1. ans = 0 while(i < n) : # If current element is 1, then # find length of segment of 1s # starting from current element. if(arr[i] == 1) : Len = 0 while(i < n and arr[i] == 1) : i += 1 Len += 1 # add number of possible # subarrays of 1 to result. ans += (Len*(Len+1)) // 2 i += 1 return ans # Function to find number of subarrays having # product exactly equal to k. def findSubarrayCount(arr, n, k) : start, endval, p, countOnes, res = 0, 0, 1, 0, 0 while (endval < n) : p = p * (arr[endval]) # If product is greater than k then we need to decrease # it. This could be done by shifting starting point of # sliding window one place to right at a time and update # product accordingly. if(p > k) : while(start <= endval and p > k) : p = p // arr[start] start += 1 if(p == k) : # Count number of succeeding ones. countOnes = 0 while endval + 1 < n and arr[endval + 1] == 1 : countOnes += 1 endval += 1 # Update result by adding both new subarray # and effect of succeeding ones. res += (countOnes + 1) # Update sliding window and result according # to change in sliding window. Here preceding # 1s have same effect on subarray as succeeding # 1s, so simply add. while(start <= endval and arr[start] == 1 and k!=1) : res += (countOnes + 1) start += 1 # Move start to correct position to find new # subarray and update product accordingly. p = p // arr[start] start += 1 endval += 1 return res arr1 = [ 2, 1, 1, 1, 3, 1, 1, 4 ] n1 = len(arr1) k = 1 if(k != 1) : print(findSubarrayCount(arr1, n1, k)) else : print(countOne(arr1, n1)) arr2 = [ 2, 1, 1, 1, 4, 5] n2 = len(arr2) k = 4 if(k != 1) : print(findSubarrayCount(arr2, n2, k)) else : print(countOne(arr2, n2)) # This code is contributed by divyesh072019
C#
// C# program to find number
// of subarrays having product
// exactly equal to k.
using System;
class GFG
{
// Function to find number of
// subarrays having product
// exactly equal to k.
public static int findSubarrayCount(int []arr,
int n, int k)
{
int start = 0, endval = 0;
int p = 1, countOnes = 0, res = 0;
while(endval < n)
{
p *= (arr[endval]);
// If product is greater than k
// then we need to decrease it.
// This could be done by shifting
// starting point of sliding window
// one place to right at a time and
// update product accordingly.
if (p > k)
{
while (start <= endval && p > k)
{
p /= arr[start];
start++;
}
}
if (p == k)
{
// Count number of
// succeeding ones.
countOnes = 0;
while (endval + 1 < n &&
arr[endval + 1] == 1)
{
countOnes++;
endval++;
}
// Update result by adding
// both new subarray and
// effect of succeeding ones.
res += (countOnes + 1);
// Update sliding window and
// result according to change
// in sliding window. Here
// preceding 1s have same
// effect on subarray as
// succeeding 1s, so simply add.
while (start <= endval &&
arr[start] == 1)
{
res += (countOnes + 1);
start++;
}
// Move start to correct position
// to find new subarray and update
// product accordingly.
p /= arr[start];
start++;
}
endval++;
}
return res;
}
// Driver code
public static void Main ()
{
int []arr = new int[]{ 2, 1, 1,
1, 4, 5 };
int n = arr.Length;
int k = 4;
Console.WriteLine(findSubarrayCount(arr, n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find number of subarrays
// having product exactly equal to k.
// Function to find number of subarrays
// having product exactly equal to k.
function findSubarrayCount($arr, $n, $k)
{
$start = 0;
$endval = 0;
$p = 1;
$countOnes = 0;
$res = 0;
while ($endval < $n)
{
$p *= ($arr[$endval]);
// If product is greater than k
// then we need to decrease it.
// This could be done by shifting
// starting point of sliding window
// one place to right at a time and
// update product accordingly.
if($p > $k)
{
while($start <= $endval && $p > $k)
{
$p /= $arr[$start];
$start++;
}
}
if($p == $k)
{
// Count number of
// succeeding ones.
$countOnes = 0;
while($endval + 1 < $n &&
$arr[$endval + 1] == 1)
{
$countOnes++;
$endval++;
}
// Update result by adding
// both new subarray and
// effect of succeeding ones.
$res += ($countOnes + 1);
// Update sliding window and
// result according to change
// in sliding window. Here
// preceding 1s have same
// effect on subarray as
// succeeding 1s, so simply
// add.
while($start <= $endval &&
$arr[$start] == 1)
{
$res += ($countOnes + 1);
$start++;
}
// Move start to correct
// position to find new
// subarray and update
// product accordingly.
$p /= $arr[$start];
$start++;
}
$endval++;
}
return $res;
}
// Driver Code
$arr = array(2, 1, 1, 1, 4, 5);
$n = sizeof($arr) ;
$k = 4;
echo findSubarrayCount($arr, $n, $k);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find number of subarrays
// having product exactly equal to k.
// Function to find number of subarrays
// having product equal to 1.
function countOne(arr, n)
{
let i = 0;
// To store number of ones in
// current segment of all 1s.
let len = 0;
// To store number of subarrays
// having product equal to 1.
let ans = 0;
while (i < n)
{
// If current element is 1, then
// find length of segment of 1s
// starting from current element.
if (arr[i] == 1)
{
len = 0;
while (i < n && arr[i] == 1)
{
i++;
len++;
}
// Add number of possible
// subarrays of 1 to result.
ans += parseInt((len * (len + 1)) / 2, 10);
}
i++;
}
return ans;
}
/// Function to find number of subarrays having
/// product exactly equal to k.
function findSubarrayCount(arr, n, k)
{
let start = 0, endval = 0, p = 1,
countOnes = 0, res = 0;
while (endval < n)
{
p *= (arr[endval]);
// If product is greater than k then we
// need to decrease it. This could be
// done by shifting starting point of
// sliding window one place to right
// at a time and update product accordingly.
if (p > k)
{
while (start <= endval && p > k)
{
p = parseInt(p / arr[start], 10);
start++;
}
}
if (p == k)
{
// Count number of succeeding ones.
countOnes = 0;
while (endval + 1 < n && arr[endval + 1] == 1)
{
countOnes++;
endval++;
}
// Update result by adding both new subarray
// and effect of succeeding ones.
res += (countOnes + 1);
// Update sliding window and result according
// to change in sliding window. Here preceding
// 1s have same effect on subarray as succeeding
// 1s, so simply add.
while(start <= endval &&
arr[start] == 1 && k != 1)
{
res += (countOnes + 1);
start++;
}
// Move start to correct position to find new
// subarray and update product accordingly.
p = parseInt(p / arr[start], 10);
start++;
}
endval++;
}
return res;
}
// Driver code
let arr1 = [ 2, 1, 1, 1, 3, 1, 1, 4 ];
let n1 = arr1.length;
let k = 1;
if (k != 1)
document.write(findSubarrayCount(arr1, n1, k) + "</br>");
else
document.write(countOne(arr1, n1) + "</br>");
let arr2 = [ 2, 1, 1, 1, 4, 5 ];
let n2 = arr2.length;
k = 4;
if (k != 1)
document.write(findSubarrayCount(arr2, n2, k) + "</br>");
else
document.write(countOne(arr2, n2) + "</br>");
// This code is contributed by suresh07
</script>
9 4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)