Dada una array de números positivos, calcule el número de posibles subarreglos contiguos que tengan un producto menor que un número K dado.
Ejemplos:
Input : arr[] = [1, 2, 3, 4]
K = 10
Output : 7
The subarrays are {1}, {2}, {3}, {4}
{1, 2}, {1, 2, 3} and {2, 3}
Input : arr[] = [1, 9, 2, 8, 6, 4, 3]
K = 100
Output : 16
Input : arr[] = [10, 5, 2, 6]
K = 100
Output : 8
Un enfoque ingenuo para este problema es generar todos los subarreglos del arreglo y luego contar el número de arreglos que tienen un producto menor que K.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to count subarrays having
// product less than k.
#include <iostream>
using namespace std;
int countsubarray(int array[], int n, int k)
{
int count = 0;
int i, j, mul;
for (i = 0; i < n; i++) {
// Counter for single element
if (array[i] < k)
count++;
mul = array[i];
for (j = i + 1; j < n; j++) {
// Multiple subarray
mul = mul * array[j];
// If this multiple is less
// than k, then increment
if (mul < k)
count++;
else
break;
}
}
return count;
}
// Driver Code
int main()
{
int array[] = { 1, 2, 3, 4 };
int k = 10;
int size = sizeof(array) / sizeof(array[0]);
int count = countsubarray(array, size, k);
cout << count << "\n";
}
// This code is contributed by 'Dev Agarwal'.
Java
// Java program to count subarrays
// having product less than k.
class GFG {
static int countsubarray(int array[], int n, int k)
{
int count = 0;
int i, j, mul;
for (i = 0; i < n; i++) {
// Counter for single element
if (array[i] < k)
count++;
mul = array[i];
for (j = i + 1; j < n; j++) {
// Multiple subarray
mul = mul * array[j];
// If this multiple is less
// than k, then increment
if (mul < k)
count++;
else
break;
}
}
return count;
}
// Driver Code
public static void main(String args[])
{
int array[] = { 1, 2, 3, 4 };
int k = 10;
int size = array.length;
int count = countsubarray(array, size, k);
System.out.print(count);
}
}
// This code is contributed by Sam007
Python3
# Python3 program to count subarrays # having product less than k. def countsubarray(array, n, k): count = 0 for i in range(0, n): # Counter for single element if array[i] < k: count += 1 mul = array[i] for j in range(i + 1, n): # Multiple subarray mul = mul * array[j] # If this multiple is less # than k, then increment if mul < k: count += 1 else: break return count # Driver Code array = [1, 2, 3, 4] k = 10 size = len(array) count = countsubarray(array, size, k) print(count, end=" ") # This code is contributed by Shreyanshi Arun.
C#
// C# program to count subarrays having
// product less than k.
using System;
public class GFG {
static int countsubarray(int[] array, int n, int k)
{
int count = 0;
int i, j, mul;
for (i = 0; i < n; i++) {
// Counter for single element
if (array[i] < k)
count++;
mul = array[i];
for (j = i + 1; j < n; j++) {
// Multiple subarray
mul = mul * array[j];
// If this multiple is less
// than k, then increment
if (mul < k)
count++;
else
break;
}
}
return count;
}
// Driver Code
static public void Main()
{
int[] array = { 1, 2, 3, 4 };
int k = 10;
int size = array.Length;
int count = countsubarray(array, size, k);
Console.WriteLine(count);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to count subarrays
// having product less than k.
// function that returns count
function countsubarray($array, $n, $k)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
{
// Counter for single element
if ($array[$i] < $k)
$count++;
$mul = $array[$i];
for ($j = $i + 1; $j < $n; $j++)
{
// Multiple subarray
$mul = $mul * $array[$j];
// If this multiple is less
// than k, then increment
if ($mul < $k)
$count++;
else
break;
}
}
return $count;
}
// Driver Code
$array = array(1, 2, 3, 4);
$k = 10;
$size = sizeof($array);
$count = countsubarray($array, $size, $k);
echo($count . "\n");
// This code is contributed by Ajit.
?>
Javascript
<script>
// javascript program to count subarrays
// having product less than k.
function countsubarray(array , n , k)
{
var count = 0;
var i, j, mul;
for (i = 0; i < n; i++)
{
// Counter for single element
if (array[i] < k)
count++;
mul = array[i];
for (j = i + 1; j < n; j++)
{
// Multiple subarray
mul = mul * array[j];
// If this multiple is less
// than k, then increment
if (mul < k)
count++;
else
break;
}
}
return count;
}
// Driver Code
var array = [ 1, 2, 3, 4 ];
var k = 10;
var size = array.length;
var count = countsubarray(array, size, k);
document.write(count);
// This code is contributed by todaysgaurav
</script>
Producción
7
Complejidad del tiempo: O(n^2).
Podemos optimizar el enfoque basado en la técnica de la ventana deslizante (tenga en cuenta que necesitamos encontrar partes contiguas)
En primer lugar, de acuerdo con la descripción, todos los elementos de la array son estrictamente positivos. También supongamos que el producto de todos los elementos de la array siempre se ajusta al tipo de entero de 64 bits. Teniendo en cuenta estos dos puntos, podemos multiplicar y dividir los elementos de la array de forma segura (sin división por cero, sin desbordamientos).
Veamos cómo contar la cantidad deseada. Supongamos que tenemos una ventana entre el inicio y el final, y el producto de todos sus elementos es p < k. Ahora, intentemos agregar un nuevo elemento x.
Hay dos casos posibles.
Caso 1. p*x < k
Esto significa que podemos mover el límite derecho de la ventana un paso más allá. ¿Cuántas arrays contiguas produce este paso? Es: 1 + (final-inicio).
De hecho, el elemento en sí comprende una array, y también podemos agregar x a todas las arrays contiguas que tienen un borde derecho al final. Hay tantas arrays como la longitud de la ventana.Caso 2. p*x >= k
Esto significa que primero debemos ajustar el borde izquierdo de la ventana para que el producto sea nuevamente menor que k. Después de eso, podemos aplicar la fórmula del Caso 1.
Ejemplo :
a = [5, 3, 2] k = 16 counter = 0 Window: [5] Product: 5 5 counter += 1+ (0-0) counter = 1 Window: [5,3] Product: 15 15 counter += 1 + (1-0) counter = 3 Window: [5,3,2] Product: 30 30 > 16 --> Adjust the left border New Window: [3,2] New Product: 6 6 counter += 1 + (2-1) counter = 5 Answer: 5
Implementación:
C++
// CPP program to count subarrays having product
// less than k.
#include <iostream>
#include <vector>
using namespace std;
int countSubArrayProductLessThanK(const vector<int>& a,
long long k)
{
const int n = a.size();
long long p = 1;
int res = 0;
for (int start = 0, end = 0; end < n; end++) {
// Move right bound by 1 step. Update the product.
p *= a[end];
// Move left bound so guarantee that p is again
// less than k.
while (start < end && p >= k)
p /= a[start++];
// If p is less than k, update the counter.
// Note that this is working even for (start ==
// end): it means that the previous window cannot
// grow anymore and a single array element is the
// only addendum.
if (p < k) {
int len = end - start + 1;
res += len;
}
}
return res;
}
// Driver Code
int main()
{
// Function Calls
cout << countSubArrayProductLessThanK({ 1, 2, 3, 4 },
10)
<< endl;
cout << countSubArrayProductLessThanK(
{ 1, 9, 2, 8, 6, 4, 3 }, 100)
<< endl;
cout << countSubArrayProductLessThanK({ 5, 3, 2 }, 16)
<< endl;
cout << countSubArrayProductLessThanK({ 100, 200 }, 100)
<< endl;
cout << countSubArrayProductLessThanK({ 100, 200 }, 101)
<< endl;
}
Java
// Java program to count subarrays having
// product less than k.
import java.util.*;
class GFG {
static int
countSubArrayProductLessThanK(ArrayList<Integer> a,
long k)
{
int n = a.size();
long p = 1;
int res = 0;
for (int start = 0, end = 0; end < n; end++) {
// Move right bound by 1 step.
// Update the product.
p *= a.get(end);
// Move left bound so guarantee that
// p is again less than k.
while (start < end && p >= k)
p /= a.get(start++);
// If p is less than k, update the counter.
// Note that this is working even for
// (start == end): it means that the
// previous window cannot grow anymore
// and a single array element is the only
// addendum.
if (p < k) {
int len = end - start + 1;
res += len;
}
}
return res;
}
// Drive Code
public static void main(String[] args)
{
// Function Calls
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(1);
al.add(2);
al.add(3);
al.add(4);
System.out.println(
countSubArrayProductLessThanK(al, 10));
ArrayList<Integer> al1 = new ArrayList<Integer>();
al1.add(1);
al1.add(9);
al1.add(2);
al1.add(8);
al1.add(6);
al1.add(4);
al1.add(3);
System.out.println(
countSubArrayProductLessThanK(al1, 100));
ArrayList<Integer> al2 = new ArrayList<Integer>();
al2.add(5);
al2.add(3);
al2.add(2);
System.out.println(
countSubArrayProductLessThanK(al2, 16));
ArrayList<Integer> al3 = new ArrayList<Integer>();
al3.add(100);
al3.add(200);
System.out.println(
countSubArrayProductLessThanK(al3, 100));
ArrayList<Integer> al4 = new ArrayList<Integer>();
al4.add(100);
al4.add(200);
System.out.println(
countSubArrayProductLessThanK(al3, 101));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to count # subarrays having product # less than k. def countSubArrayProductLessThanK(a, k): n = len(a) p = 1 res = 0 start = 0 end = 0 while(end < n): # Move right bound by 1 # step. Update the product. p *= a[end] # Move left bound so guarantee # that p is again less than k. while (start < end and p >= k): p = int(p//a[start]) start += 1 # If p is less than k, update # the counter. Note that this # is working even for (start == end): # it means that the previous # window cannot grow anymore # and a single array element # is the only addendum. if (p < k): l = end - start + 1 res += l end += 1 return res # Driver Code if __name__ == '__main__': print(countSubArrayProductLessThanK([1, 2, 3, 4], 10)) print(countSubArrayProductLessThanK([1, 9, 2, 8, 6, 4, 3], 100)) print(countSubArrayProductLessThanK([5, 3, 2], 16)) print(countSubArrayProductLessThanK([100, 200], 100)) print(countSubArrayProductLessThanK([100, 200], 101)) # This code is contributed by mits
C#
// C# program to count subarrays
// having product less than k.
using System;
using System.Collections;
class GFG {
static int countSubArrayProductLessThanK(ArrayList a,
int k)
{
int n = a.Count;
int p = 1;
int res = 0;
for (int start = 0, end = 0; end < n; end++) {
// Move right bound by 1 step.
// Update the product.
p *= (int)a[end];
// Move left bound so guarantee
// that p is again less than k.
while (start < end && p >= k)
p /= (int)a[start++];
// If p is less than k, update the
// counter. Note that this is working
// even for (start == end): it means
// that the previous window cannot
// grow anymore and a single array
// element is the only Addendum.
if (p < k) {
int len = end - start + 1;
res += len;
}
}
return res;
}
// Driver Code
static void Main()
{
ArrayList al = new ArrayList();
al.Add(1);
al.Add(2);
al.Add(3);
al.Add(4);
Console.WriteLine(
countSubArrayProductLessThanK(al, 10));
ArrayList al1 = new ArrayList();
al1.Add(1);
al1.Add(9);
al1.Add(2);
al1.Add(8);
al1.Add(6);
al1.Add(4);
al1.Add(3);
Console.WriteLine(
countSubArrayProductLessThanK(al1, 100));
ArrayList al2 = new ArrayList();
al2.Add(5);
al2.Add(3);
al2.Add(2);
Console.WriteLine(
countSubArrayProductLessThanK(al2, 16));
ArrayList al3 = new ArrayList();
al3.Add(100);
al3.Add(200);
Console.WriteLine(
countSubArrayProductLessThanK(al3, 100));
ArrayList al4 = new ArrayList();
al4.Add(100);
al4.Add(200);
Console.WriteLine(
countSubArrayProductLessThanK(al3, 101));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to count
// subarrays having product
// less than k.
function countSubArrayProductLessThanK($a,$k)
{
$n = count($a);
$p = 1;
$res = 0;
for ($start = 0, $end = 0;
$end < $n; $end++)
{
// Move right bound by 1
// step. Update the product.
$p *= $a[$end];
// Move left bound so guarantee
// that p is again less than k.
while ($start < $end &&
$p >= $k)
$p /= $a[$start++];
// If p is less than k, update
// the counter. Note that this
// is working even for (start == end):
// it means that the previous
// window cannot grow anymore
// and a single array element
// is the only addendum.
if ($p < $k)
{
$len = $end - $start + 1;
$res += $len;
}
}
return $res;
}
// Driver Code
echo countSubArrayProductLessThanK(
array(1, 2, 3, 4), 10) . "\n";
echo countSubArrayProductLessThanK(
array(1, 9, 2, 8, 6, 4, 3), 100) . "\n";
echo countSubArrayProductLessThanK(
array(5, 3, 2), 16) . "\n";
echo countSubArrayProductLessThanK(
array(100, 200), 100) . "\n";
echo countSubArrayProductLessThanK(
array(100, 200), 101) . "\n";
// This code is contributed by mits
?>
Javascript
<script>
// js program to count subarrays having product
// less than k.
function countSubArrayProductLessThanK(a, k)
{
let n = a.length;
let p = 1;
let res = 0;
for (let start = 0, end = 0; end < n; end++) {
// Move right bound by 1 step. Update the product.
p *= a[end];
// Move left bound so guarantee that p is again
// less than k.
while (start < end && p >= k)
p =Math.floor(p/ a[start++]);
// If p is less than k, update the counter.
// Note that this is working even for (start ==
// end): it means that the previous window cannot
// grow anymore and a single array element is the
// only addendum.
if (p < k) {
let len = end - start + 1;
res += len;
}
}
return res;
}
// Driver Code
document.write(countSubArrayProductLessThanK([1, 2, 3, 4], 10),'<br>')
document.write(countSubArrayProductLessThanK([1, 9, 2, 8, 6, 4, 3], 100),'<br>')
document.write(countSubArrayProductLessThanK([5, 3, 2], 16),'<br>')
document.write(countSubArrayProductLessThanK([100, 200], 100),'<br>')
document.write(countSubArrayProductLessThanK([100, 200], 101),'<br>')
</script>
Producción
7 16 5 0 1
Complejidades: cada elemento de la array se accede como máximo dos veces, por lo tanto, es una complejidad de tiempo O (n) . Se utilizan algunas variables escalares, por lo tanto, es O(1) espacio adicional .
Ejercicio 1: actualice la solución para que pueda manejar ceros en la array de entrada.
Ejercicio 2: actualice la solución para que pueda manejar el desbordamiento de la multiplicación al calcular los productos.
Este artículo es una contribución de Raghav Sharma y mejorado por Andrey Khayrutdinov . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA