Last Updated: 27 Feb, 2021
Count Subarrays Having Product Less Than K
Moderate
Asked in companies
You are given an array ‘ARR’ consist of ‘N’ positive integers, and a positive integer ‘K’.
Your task is to count and return the number of contiguous subarrays having products of their elements strictly less than ‘K’.
Example:
Consider an array ARR = [1, 2, 3, 4, 5], and K = 7, then all the subarrays having product less than 7 are [1], [2], [3], [4], [5], [1, 2], [2,3], [1,2,3] i.e there is total 8 subarays having product less than 7.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2*T lines represent the ‘T’ test cases.
The first line contains two space-separated integers ‘N’ and ‘K’ respectively.
The second line contains ‘N’ space-separated positive integers denoting the array ‘ARR’.
Output format :
For each test case, print a single line containing a single integer denoting integer representing the count of the number of contiguous subarrays having products of their elements strictly less than ‘K’.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10 ^ 4
1 <= K <= 10 ^ 8
1 <= ARR[i] <= 10 ^ 4
Where ‘T’ is the total number of test cases, ‘N’ is the number of elements in the given array ‘Arr’, ‘K’ is the given integer, and ‘ARR[i]’ is the element of the given array ‘ARR’.
Time limit: 1 sec
Approaches
In this approach, we will one by one find the product of each subarray and increment the counter by ‘1’ if we find the subarray having the product of its elements less than ‘K’.
Algorithm
- Initialize an integer variable ‘counter’:= 0.
- Run a loop where ‘i’ ranges from 0 to N - 1 and for each ‘i’ do the following -:
- Initialize an integer variable ‘product’:= 1.
- Run a loop where ‘j’ ranges from ‘i’ to ‘N - 1’ and for each ‘j’ do the following -:
- Multiply Arr[j] with ‘product’, i.e product := product * Arr[j].
- If ‘product’ < ‘K’ then increment the counter by 1, Otherwise break the loop,
- Return counter.
Note that you may need to take care of integer overflow in this approach.
We can solve this problem by using an optimized approach based on the sliding windows technique. We will keep two pointers start and end representing the start and end of the sliding windows and integer variable ‘product’ having the product of all integers in the current window. Initially ‘start’:= 0, ‘end’:= 0, and ‘product’:= 1, Current window have all integer between index start and end, excluding end. We also initialize an integer variable ‘counter’:= 0, it will keep the count of the number of subarrays having the product less than ‘K’.
Now we move the sliding window, till end < N, and in each step, we check whether we can move the right bound of the sliding window further i.e check whether Arr[end] * product < K or not, if yes we multiply ‘product’ by Arr[end], increment ‘end’ by ‘1’ and then we will increment the counter by end-start as the number of subarrays having product less than ‘K’ and ending at end-1 will be end-start. Otherwise, we will divide the product by Arr[start] and increment start by ‘1’.
Algorithm
- Initialize integer variables ‘start’:= 0, ‘end’:= 0, ‘product’:= 1 and ‘counter’:= 0.
- Run a loop till end < N and in each iteration we do the following-:
- If Arr[end]*product < K, then do product *= Arr[end], end = end+1, and counter = counter + end - start;
- Otherwise, If start = end, then increment both ‘start’, ‘end ‘by ‘1’ as it means element at index start is greater equal to ‘K’ so sliding windows cannot have this element, and if start != end, then divide do product /= Arr[start], start = start + 1.
- Return counter.
Note that you may need to take care of integer overflow in this approach.
Similar problems