Given an array of positive numbers, calculate the number of possible contiguous subarrays having product lesser than a given number K.
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 : 16Input : arr[] = [10, 5, 2, 6]
K = 100
Output : 8
Try it on GfG Practice
Table of Content
[Naive Approach] Checking Each Subarray - O(n^2) time and O(1) space
Generate all subarrays of the array and then count the number of arrays 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;
}
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";
}
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;
}
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);
}
}
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
array = [1, 2, 3, 4]
k = 10
size = len(array)
count = countsubarray(array, size, k)
print(count, end=" ")
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;
}
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);
}
}
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);
console.log(count);
Output
7
[Expected Approach] Using Sliding Window Approach - O(n) time and O(1) space
- Use sliding window for contiguous subarrays; Since elements are positive, we can safely multiply and divide to maintain the product.
- Maintain a window (start → end) with product < k; if it becomes ≥ k, move
startforward.- There are two possible cases.
Case 1. p*x < k : This means we can move the window's right bound one step further. How many contiguous arrays does this step produce? It is: 1 + (end-start). Indeed, the element itself comprises an array, and also we can add x to all contiguous arrays which have right border at end. There are as many such arrays as the length of the window.
Case 2. p*x >= k : This means we must first adjust the window's left border so that the product is again less than k. After that, we can apply the formula from Case 1.
Example :
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
#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 < k, update the count; this also works when start == end,
//meaning only the single element forms the window.
if (p < k) {
int len = end - start + 1;
res += len;
}
}
return res;
}
int main()
{
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;
}
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 < k, update the count; this also works when start == end,
//meaning only the single element forms the window.
if (p < k) {
int len = end - start + 1;
res += len;
}
}
return res;
}
public static void main(String[] args)
{
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));
}
}
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 < k, update the count; this also works when start == end,
# meaning only the single element forms the window.
if (p < k):
l = end - start + 1
res += l
end += 1
return res
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))
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 < k, update the count; this also works when start == end,
//meaning only the single element forms the window.
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));
}
}
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 < k, update the count; this also works when start == end,
//meaning only the single element forms the window.
if (p < k) {
let len = end - start + 1;
res += len;
}
}
return res;
}
// Driver Code
console.log(countSubArrayProductLessThanK([1, 2, 3, 4], 10),'<br>')
console.log(countSubArrayProductLessThanK([1, 9, 2, 8, 6, 4, 3], 100),'<br>')
console.log(countSubArrayProductLessThanK([5, 3, 2], 16),'<br>')
console.log(countSubArrayProductLessThanK([100, 200], 100),'<br>')
console.log(countSubArrayProductLessThanK([100, 200], 101),'<br>')
Output
7 16 5 0 1
Exercise 1: Update the solution so that it could handle nils in the input array.
Exercise 2: Update the solution so that it could handle multiplication overflow when computing products.