**Objective**: Given an array of positive integers and integer ‘K’. Write an algorithm to count all the possible sub arrays where product of all the elements in the sub array is less than k.

**Example:**

Int [] nums = {10, 4, 2, 6}; K = 100Output: 9 Sub arrays: [10], [10 4], [10, 4, 2], [4], [4, 2], [4, 2, 6], [2], [2, 6], [6]

**Approach:**

- Calculate all the possible subarrays as discussed here (Print all subarrays of a given array).
- Find out which array has elements has product less than k.

**Time complexity: O(n^3)**

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class SubarrayProductLessThanK { | |

public int find(int [] arrA, int k){ | |

int result=0; | |

int arrSize = arrA.length; | |

//start point | |

for (int startPoint = 0; startPoint <arrSize ; startPoint++) { | |

//group sizes | |

for (int grps = startPoint; grps <=arrSize ; grps++) { | |

//if start point = 1 then | |

//grp size = 1 , take 10 | |

//grp size = 2, take 10 4 | |

//grp size = 3, take 10 4 2 ans so on | |

int product=1; | |

int noElements=0; | |

String tempSubArrrays =""; | |

for (int j = startPoint ; j < grps ; j++) { | |

tempSubArrrays += arrA[j] + " "; | |

product *= arrA[j]; | |

noElements++; | |

} | |

if(product<k && noElements>0){ | |

System.out.print(tempSubArrrays); | |

result++; | |

System.out.println(); | |

} | |

} | |

} | |

return result; | |

} | |

public static void main(String[] args) { | |

SubarrayProductLessThanK s = new SubarrayProductLessThanK(); | |

int [] nums = {10,4,2,6}; | |

int k = 100; | |

System.out.println("Sub arrays has sum less than k=100 are: " + s.find(nums, k)); | |

} | |

} |

**Output:**

10 10 4 10 4 2 4 4 2 4 2 6 2 2 6 6 Sub arrays has sum less than k=100 are: 9

**Use Sliding window approach: O(n)**

- We recommend to read about “Sliding Window Algorithm” before continue.
- Every time any new element is added to the sub array then there are possibilities either the product of the elements will be less than k or greater than equal to k.
- Start with first element and keep adding elements till the product of elements are less than K.
- Once the product is greater than k than, start dividing the product with elements of sub array, from the start index of that particular sub array.
- Repeat the above 2 steps till we navigate the entire array.
- Now let’s discuss how will count the sub arrays.
- If product of all the elements in array is less than K that means all the subarrays will also have product less than K.
- Let’s say we have 3 elements in the subarray where product is less than k and after adding the 4th element in subarray, product is still less then we will have 3 more subarrays(same as the previous size of array) in our result see the explanation below
- [1, 2, 3], K = 40. Add another element 4 so new window with product less than 40 is [1, 2, 3, 4]. So all the new subarrays with product less than 40 will be – {1, 2, 3, 4}, {2, 3, 4}, {3, 4}, {4}.

Let’s take one Example, have 2 pointers start and end to track the sliding window

int [] nums = {10, 4, 2, 6}; K = 100 count = 0 (will be our final result) __________________________________________________________ start = 0, end = 1: [10], product = 10 <100, count = count + end-start = 0 + 1 = 1 __________________________________________________________ start = 0, end = 2: [10, 4], product = 10*4 = 40 <100, count = count + end-start = 1 + 2 = 3 (new ones are {10, 4}, {4}) ___________________________________________________________ start = 0, end = 3: [10, 4, 2], product = 40*2 = 80 <100, count = count + end-start = 3 + 3 = 6 (new ones are {10, 4, 2}, {4, 2}, {2}) ___________________________________________________________ start = 0, end = 4: [10, 4, 2, 6], product = 80*6 = 480 > 100 => remove 10 and product = 480/10 = 48, start = 1 ___________________________________________________________ start = 1, end = 4: [4, 2, 6], product = 48<100, count = count + end-start =6 + 4 – 1 = 9

**Time complexity: O(n)**

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class SubarrayProductLessThanK_Better { | |

public int countSubArraysProudctLessThanK(int [] arr, int k){ | |

int start = 0; | |

int end = 1; | |

long product = arr[0]; | |

int count = 0; | |

while (start <= end && end <= arr.length) { | |

if (product < k) { | |

count += end – start; | |

if (end < arr.length) product *= arr[end]; | |

end++; | |

} else { | |

product /= arr[start++]; | |

} | |

} | |

return count; | |

} | |

public static void main(String[] args) { | |

SubarrayProductLessThanK_Better s = new SubarrayProductLessThanK_Better(); | |

int [] nums = {10,4,2,6}; | |

int k = 100; | |

System.out.println("No of sub arrays has sum less than k="+k+" are: " + | |

s.countSubArraysProudctLessThanK(nums,k)); | |

} | |

} |

**Output**:

No of sub arrays has sum less than k=100 are: 9

I think the example in the question has some problems. [10 2] [4 6] their products are less than 100 but is not in the output.

The question is to print subarray which means contiguous elements , do not confuse it with sub sequence.

This solution could be done O(n^2). pls check the below code:

public class SubarrayProductLessThanK {

public static void main(String args[]) {

int[] nums = { 10, 4, 2, 6 };

int k = 100;

for (int i = 0; i < nums.length; i++) {

int prod = nums[i];

String tempSubArray = nums[i] + "";

if (prod < k) {

System.out.println(nums[i]);

if (i == nums.length – 1) {

break;

}

for (int j = i + 1; j < nums.length; j++) {

prod = prod * nums[j];

tempSubArray = tempSubArray + "," + nums[j];

if (prod < k) {

System.out.println(tempSubArray);

} else {

break;

}

}

}

}

}

}