Count Subarrays Having Product Less Than K

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
13 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 )
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
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
Hint

Find the product of each subarray.

Approaches (2)
Brute Force

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.

Time Complexity

O(N ^ 2), where ‘N’ is the number of elements in the given array ‘ARR’

 

In the worst-case both inner and outer loops run ‘N’ times, Thus overall time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

We are using constant extra space here.

Code Solution
(100% EXP penalty)
Count Subarrays Having Product Less Than K
Full screen
Console