Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Count Subarrays Having Product Less Than K

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
Goldman SachsXoriantJUSPAY

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 7
7
5 7
1 2 3 4 5
Sample Output 1:
0
8
Explanation of Sample Input 1:
Test case 1:
There is only one element in ‘ARR’ i.e 7, so it has only one subarray i.e [7]. The product of all elements of this subarray will be 7 which is equal to 7, thus there is no subarray having product strictly less than 7  

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
5 100
1 2 3 4 5
2 10
10 9
Sample Output 2:
13
1
Full screen
Console